0
$\begingroup$

Here on page 367 there is an example of $\text{dist}\mathbb{NP}$-complete problem: let $U$ contain all tuples $\langle M,x,1^t\rangle$ where there exists a string $y\in \{0,1\}^l$such that the nondeterministic $TM$ $M$ outputs $1$ on input $x$ within $t$ steps.

For every $n$, we let $\cal U_n$ be the following distribution on length $n$ tuples $\langle M,x,1^t\rangle$: the string representing $M$ is chosen at random from all strings of length at most $\log n$, $t$ is chosen at random in the set $\{0,\ldots,n-|M|\}$ and $x$ is chosen at random from $\{0,1\}^{n-t-|M|}$.This distribution is polynomial time computable.

Then $\langle U,\cal U \rangle$ is $\text{dist}\mathbb{NP}$-complete.

BUT those $l$ and $y$ are never used later on in this definition! What is wrong?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.