4
votes
Accepted
Can the time complexity of verifying a solution ever be greater than the complexity of the solution
This is possible when a problem has multiple solutions, and the time complexity of generating a single solution is lower than the time complexity of generating all solutions.
For example, consider the ...
- 30k
3
votes
Accepted
BPP, probabilistic-poly-time reduction
By making several independent runs of the machine and taking a majority vote, you can reduce the probability of error of a BPP machine for $B$ below $1/12$ (scroll down to the last paragraph of ...
- 1,716
2
votes
Accepted
self reducible in p-time
Yes. Here is how to build a polynomial-time algorithm. It has hardcoded the list of all $x \in L$ whose length is $\le n_0$. For any longer $x$, keep applying $f(\cdot)$ until the result has length ...
D.W.♦
- 164k
2
votes
self-reducible in NP-time
Yes. The certificate for $x \in L$ is a list of indices $i_1,i_2,\dots,i_m$. The verifier repeatedly applies $f$, taking the $i_1$th string output by $f$ for the first invocation of $f$, the $i_2$th ...
D.W.♦
- 164k
1
vote
Can the time complexity of verifying a solution ever be greater than the complexity of the solution
Problem: Given k, find a p such that either p=2 or p is a k digit prime.
Finding a solution: p=2 is a solution.
Verification: I give you a k digit number. Please verify that k is a prime.
- 31.5k
1
vote
Accepted
PSPACE, probabilistic-poly-time reduction
PSPACE is the class of languages that can be decided by a deterministic Turing machine using polynomial space.
The goal is to show that if $B \in \text{PSPACE}$ , then $A \in \text{PSPACE}$.
Since $...
- 145
Only top scored, non community-wiki answers of a minimum length are eligible