# Tag Info

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 ...
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
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 ...
• 164k

### 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 ...
• 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