Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Tag Info

2

A language $L$ is in $\mathsf{PCP}(r(n),q(n))$ if there is a randomized polytime algorithm $V(x,y)$ which acts as follows: The algorithm is given $r(n)$ random bits. Given these random bits, it chooses (deterministically) $q(n)$ locations in $y$. It reads $y$ at these locations, and based on that, decides whether to accept or reject. Furthermore, $V$ ...

0

If you prove that P=NP then proving the opposite is not just harder, but impossible.

-2

I believe it is impossible to prove P<>NP, because you would have to rule out all algorithms that could prove P=NP. There could be an infinite number of these possible. There is no way to disprove infinity, therefore it’s not possible. On the other hand all it would take is a single algorithm to prove P=NP, if it is so. Therefore, either P=NP which ...

0

Polynomial reduction and certificates have very little to do with each other. Basically, we defined the set P of all easy problems that can be solved by a computer in polynomial time. Then obviously problems not in P are hard. We then defined the set NP of all problems which can be solved in polynomial time by a non-deterministic computer, in other ...

4

As the original paper is showing a lot more, I use this one at page 69-70, Theorem 3.9, as this is the proof I also know. As you can see there, the complete statement of Baker, Gill, Solovay is: There exist oracles $A, B$ s.t. $P^A = NP^A$ and $P^B \neq NP^B$ The second oracle cannot be considered a counterexample for $P = NP$ because you cannot "...

Top 50 recent answers are included