New answers tagged polynomial-time
2
Assuming you mean "polynomial in the size of the binary representation of K and M", then it is extremely unlikely, but proving that it is impossible will also be very difficult.
There are polynomial time algorithms for checking primality, but they would be applied to a number whose size is K, which is a lot bigger than checking a number whose size ...
2
No. If the problem was polynomial-time verifiable, it would be solvable in exponential time, and thus decidable; but we already know that is not decidable.
Why in exponential time? Because $V$ runs in time $|w|^k$, it can read at most $|w|^k$ bits of the input. So, it suffices to enumerate all possible strings $c$ of length at most $|w|^k$, and run $V$ on ...
1
I think you can force the enumeration to be only on machines with a very strict format: a hard-coded poly time "clock" at the start, and after that the rest of the TM.
This will allow you to check in poly time (not even requiring a verifier) whether a given string $p$ is a part of the enumeration
0
Proving $NP=co-NP$ doesn't necessarily mean that $P=NP$. Although, the other way around is correct:
Assume $P=NP$, then $co-NP=co-P=P=NP$.
Top 50 recent answers are included
