Computational complexity theory: Difference between revisions

Revision as of 16:45, 16 September 2002

Revision as of 16:54, 16 September 2002

Line 3:

A single "problem" is an entire set of related questions, where each question is a finite-length [[string]]. For example, the problem [[Integer factorization|''FACTORIZE'']] is: given an integer written in binary, return all of the [[prime number|prime]] factors of that number. A particular question is called an ''instance''. For example, "give the factors of the number 15" is one instance of the ''FACTORIZE'' problem.

The time complexity of a problem is the number of steps that it takes to solve an instance, as a function of the size of the instance. If an instance that is ''n'' bits long can be solved in ''n''² steps, then we say it has a time complexity of ''n''². Of course, the exact number of steps will depend on exactly what machine or language is being used. To avoid that problem, we generally use [[Big 'O']] notation]]. If a problem has time complexity O(''n''²) on one typical computer, then it will also have complexity O(''n''²) on most other computers, so this notation allows us to generalize away from the details of a particular computer.

<h2>Decision Problems</h2>