Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)\ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be decided in time polynomial in $|x|$. In this context $R_A$ is called a search problem, any $w$ such that $(x, w)\in R_A$ a witness or certificate for $x\in A$, and the poly-time decider for $R_A$ is called a verifier for $A$.
We can interpret $R_A(x,w)$ as meaning "$w$ is a correct solution to $x$."
An algorithm $\mathrm{Alg}$ solves search problem $R_A$ if $$\forall x\:(\exists w \; R_A(x,w)\implies R_A(x,\mathrm{Alg}(x))).$$
Till now I understand everything.
After then my teacher define two definitions which I couldn't find anywhere.
$R_A$ is in search-NP if $R_A$ can be computed in polynomial time, $R_A$ is polynomially bounded, and $\forall n \; R_A\subseteq\{0,1\}^n\times\{0,1\}^{\leq p(n)}.$
$R_A$ is in search-P if it is in search-NP and there exists a polytime algorithm $\mathrm{Alg}$ that solves $R_A$.
Can anybody give explanation of search-NP and search-P? Or give some references?
-
$\begingroup$ 1. What do you want to know about them? Can you elaborate on what you're looking for, i.e., what you mean by "give explanation of"? 2. I don't understand your definition search-NP. Can you explain/define it more clearly? $\endgroup$D.W.– D.W. ♦2025年11月10日 01:19:32 +00:00Commented Nov 10 at 1:19
-
$\begingroup$ @D.W. This definition defined by my teacher. I am looking for this type of terms are available in any book or somewhere else. $\endgroup$Monte_carlo– Monte_carlo2025年11月10日 05:00:38 +00:00Commented Nov 10 at 5:00
-
$\begingroup$ @EmilJeřábek I understand everything. Would you put your last two comments into an answer? I can accept. Otherwise I delete my question. $\endgroup$Monte_carlo– Monte_carlo2025年11月10日 06:36:27 +00:00Commented Nov 10 at 6:36
1 Answer 1
These classes are called FNP and FP (respectively) in the literature.
Note that "$R_A$ is polynomially bounded" is the same condition as what was presumably intended by $\forall n\:R_A\subseteq\{0,1\}^n\times\{0,1\}^{\leq p(n)}$. (Taken literally, the latter does not make much sense: since the sets $\{0,1\}^n\times\{0,1\}^{\leq p(n)}$ are disjoint for different $n$, the only way $R_A$ could be included in all of them is that $R_A=\varnothing$. The condition should be really written as $R_A\subseteq\bigcup_{n\in\mathbb N}\{0,1\}^n\times\{0,1\}^{\leq p(n)}$ or as $\forall n \:R_A\restriction\{0,1\}^n\subseteq\{0,1\}^n\times\{0,1\}^{\leq p(n)}$.)
Explore related questions
See similar questions with these tags.