Người ta có thể chủ động thời gian thực hiện không?
Câu hỏi đáng sợ này là cơ sở của một trong những lĩnh vựa nghiên cứu nhiều trong tin học, do đó cũng không ngạc nhiên là đôi khi vẫn không được giải đáp. Trước hết phải xác định thế nào là ''thời gian thực hiện''. Đương nhiên, một phép tính với rất nhiều số đưa vào máy cũ đã 10 năm, sẽ mất nhiều thời gian hơn so với cùng phép tính đó có những số nguyên nhỏ được thực hiện ở một ''quái vật'' hiện đại. Các nhà toán học đã tạo ra khái niệm thành thạo, là độ phức tạp biểu thị thời gian được chương trình xếp đặt, có liên quan với tầm cỡ với các liệu (luôn được gọi là n). Để cho khái niệm này độc lập với máy được sử dụng, người ta đã diễn tả nó bằng các phép tính sơ đẳng, chứ không theo thời gian thực. Ví dụ, người ta nói rằng một chương trình bằng n lập phương, nghĩa là khi nhân đôi cỡ các dữ liệu, thì người ta cũng nhân đôi thời gian tính toán với 2 lập phương, tức là 8, dù máy tính như thế nào.
Tiếp theo là công việc của toán học và thực hành. Ví dụ một chương trình được dùng để lập một niên giám thì nó phải chọn một danh sách có n tên. Một người lập trình chưa thành thạo thường chọn thuật toán đơn giản nhất để làm là bằng n bình phương. Nhà tin học thành thạo có thể tìm thuật toán nhanh nhất trong trường hợp này là bằng n x log(n).
Nhiều trường hợp khác gai góc hơn. Đối với một số bài toán, người ta rằng không có chương trình nào nhanh hơn mọi chương trình khác, mà chỉ có những chương trình tiến gần đến một giới hạn không thể đạt được. Khái quát hơn, rõ ràng là người ta tìm cách tránh độ phức tạp của số mũ dễ làm ''nổ tung'' thời gian tính toán.
Trên thực tế, các nhà thuật toán đã xác định hai loại bài toán lớn, được gọi là P và NP.P bao gồm tất cả các bài toán mà người ta có thể giải trong một thời gian có thể lâu, nhưng không có độ phức tạp của đa thức làm nản chí, nghĩa là nó tiến triển như một lũy thừa n. NP phải xác định cầu kỳ hơn. Người ta thấy ở đây những bài toán phải huy động mọi biện pháp để tìm ra đáp số, không bị bó buộc thời gian, nhưng phải có khả năng kiếm tra đáp số này là đúng theo độ phức tạp của đa thức. Thực ra, người ta không biết P có ≠ NP không. Đó là một trong những phỏng đoán toán học chính trong các thập kỷ vừa qua.
Trong một số trường hợp, người ta lợi dụng mức độ chậm dự kiến của máy tính, như trong mật ước học, các thuật toán dựa trên nguyên lý là không thể tìm ra thông tin bí mật trừ phi dành nhiều thời gian.
