Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the informal statement "There if functions $f$ with the range of values $= \{0,1\}$, that can't be quickly calculate but if $f(x) = 0$ than we can quickly verify that it is true (by using some oracle)".

If "quickly" mean $\in P$ than it is statement $\iff P \not=NP$.

If "quickly" mean only computability (in world with infinitely quickly computers) than it is right statement ($f$ is for example function that solve Halting problem).

How else we can define "quicly" that it is statement became right?

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.