7
$\begingroup$

Consider $X$ an $\mathsf{NP}$-complete language e.g. $3-SAT$. I'm looking for an algorithm $A$ for solving $X$ with the following property. Given $M \subset \lbrace 0, 1 \rbrace^*$ any set of words s.t. $X$ with promise $M$ is decidable in polynomial time, I require $A$ to decide $X$ with promise $M$ in polynomial time

Does such $A$ exist?

The motivation for the question comes from Levin search which would satisfy the above condition if we considered the candid search problem instead of the decision problem

Is the answer affected by adding the assumption $M \in \mathsf{P}$?

$\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.