Return to Question

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$= $\{ a: f(x)=a, x \in S \}$ where $S$ is the set of all witnesses $x$ for set $A$. If P=NP then every coNP set is efficiently samplable in Noam's sense.

The following characterization of NP is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

I am interested in the assumption that there exists a universal witness set $W \in P$ for $NP$. A set $W \in P$ is universal witness set if for every $NP$-complete set $C_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $f_i:W\to \Sigma^*$ such that $C_i=Range(f_i)$. Equivalently, every $NP$-complete set $C_i$ is definable by a relation $<f_i(w), w>$ for $w \in W$.

When does the existence of a universal witness set for $NP$ imply the impossibility of efficient sampling of $coNP$ sets? Can we prove the implication if function $f_i$ is length-increasing polynomial-time computable injection? Has anyone studied similar notions to efficient sampling characterization of $NP$?

Some evidence suggests the existence of universal witness set for $NP$. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich). Also, Yato and Seta define parsimonious ASP-reductions and state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Their ASP-reduction requires efficiently computable bijections between solutions sets.

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$= $\{ a: f(x)=a, x \in S \}$ where $S$ is the set of all witnesses $x$ for set $A$. If P=NP then every coNP set is efficiently samplable in Noam's sense.

The following characterization of NP is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

I am interested in the assumption that there exists a universal witness set $W \in P$ for $NP$. A set $W \in P$ is universal witness set if for every $NP$-complete set $C_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $f_i:W\to \Sigma^*$ such that $C_i=Range(f_i)$. Equivalently, every $NP$-complete set $C_i$ is definable by a relation $<f_i(w), w>$ for $w \in W$.

When does the existence of a universal witness set for $NP$ imply the impossibility of efficient sampling of $coNP$ sets? Can we prove the implication if function $f_i$ is length-increasing polynomial-time computable injection? Has anyone studied similar notions to efficient sampling characterization of $NP$?

Some evidence suggests the existence of universal witness set for $NP$. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich). Also, Yato and Seta define parsimonious ASP-reductions and state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Their ASP-reduction requires efficiently computable bijections between solutions sets.

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$= $\{ a: f(x)=a, x \in S \}$ where $S$ is the set of all witnesses $x$ for set $A$. If P=NP then every coNP set is efficiently samplable in Noam's sense.

The following characterization of NP is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

I am interested in the assumption that there exists a universal witness set $W \in P$ for $NP$. A set $W \in P$ is universal witness set if for every $NP$-complete set $C_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $f_i:W\to \Sigma^*$ such that $C_i=Range(f_i)$. Equivalently, every $NP$-complete set is definable by a relation $<f_i(w), w>$ for $w \in W$.

When does the existence of a universal witness set for $NP$ implies the impossibility of efficient sampling of $coNP$ sets? Can we prove the implication if function $f_i$ is length-increasing injection? Has anyone studied similar notions to efficient sampling characterization of $NP$?

Some evidence suggests the existence of universal witness set for $NP$. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich). Also, Yato and Seta define parsimonious ASP-reductions and state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Their ASP-reduction requires efficiently computable bijections between solutions sets.

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$= $\{ a: f(x)=a, x \in S \}$ where $S$ is the set of all witnesses $x$ for set $A$. If P=NP then every coNP set is efficiently samplable in Noam's sense.

The following characterization of NP is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

I am interested in the assumption that there exists a universal witness set $W \in P$ for $NP$. A set $W \in P$ is universal witness set if for every $NP$-complete set $C_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $f_i:W\to \Sigma^*$ such that $C_i=Range(f_i)$. Equivalently, every $NP$-complete set $C_i$ is definable by a relation $<f_i(w), w>$ for $w \in W$.

When does the existence of a universal witness set for $NP$ imply the impossibility of efficient sampling of $coNP$ sets? Can we prove the implication if function $f_i$ is length-increasing polynomial-time computable injection? Has anyone studied similar notions to efficient sampling characterization of $NP$?

Some evidence suggests the existence of universal witness set for $NP$. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich). Also, Yato and Seta define parsimonious ASP-reductions and state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Their ASP-reduction requires efficiently computable bijections between solutions sets.

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$= $\{ a: f(x)=a, x \in S \}$ where $S$ is the set of all witnesses $x$ for set $A$. If P=NP then every coNP set is efficiently samplable in Noam's sense.

The following characterization of NP is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

I am interested in the assumption that there exists a universal witness set $W \in P$ such that for every $NP$-complete set $C_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $f_i:W\to \Sigma^*$ such that $C_i=Range(f_i)$. Equivalently, every $NP$-complete set is definable by a relation $<f_i(w), w>$ for $w \in W$.

When does the existence of a universal witness set for $NP$ implies the impossibility of efficient sampling of $coNP$ sets? Can we prove the implication if function $f_i$ is length-increasing injection? Has anyone studied similar notions to efficient sampling characterization of $NP$?

Some evidence suggests the existence of universal witness set for $NP$. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich). Also, Yato and Seta define parsimonious ASP-reductions and state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Their ASP-reduction requires a efficiently computable bijections between solutions sets.

Inspired by this answer given by Noam, which (I think) implies that a set $A \in NP$ if and only if there is polynomial-time computable function $f$ from random strings to elements of $A$ such that $A$= $\{ a: f(x)=a, x \in S \}$ where $S$ is the set of all witnesses $x$ for set $A$. If P=NP then every coNP set is efficiently samplable in Noam's sense.

The following characterization of NP is taken from Theory of computational complexity;

"A binary relation $R \subseteq\Sigma^* \times \Sigma^*$ is called polynomial honest if there exists a polynomial function $p$ such that $<x,y> \in R$ only if $|x|\le p(|y|)$ and $|y|\le p(|x|)$. A function $f:\Sigma^* \to \Sigma^*$ is polynomially honest if the relation $\{ <x, f(x)>: x\in \Sigma^*\}$ is polynomial honest.

Therefore, $A \subseteq \Sigma^*$ is in $NP$ if and only if $A=Range(f)$ for some polynomial honest and polynomial time computable function $f$."

I am interested in the assumption that there exists a universal witness set $W \in P$ for $NP$. A set $W \in P$ is universal witness set if for every $NP$-complete set $C_i \subseteq \Sigma^*$ there is some polynomially honest and polynomial-time computable function $f_i:W\to \Sigma^*$ such that $C_i=Range(f_i)$. Equivalently, every $NP$-complete set is definable by a relation $<f_i(w), w>$ for $w \in W$.

When does the existence of a universal witness set for $NP$ implies the impossibility of efficient sampling of $coNP$ sets? Can we prove the implication if function $f_i$ is length-increasing injection? Has anyone studied similar notions to efficient sampling characterization of $NP$?

Some evidence suggests the existence of universal witness set for $NP$. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich). Also, Yato and Seta define parsimonious ASP-reductions and state that $ASP$-completeness imply $NP$-completeness (Page 2, second paragraph). Their ASP-reduction requires efficiently computable bijections between solutions sets.