1
$\begingroup$

Problem Statement: Given a Problem $(A)$ such that: Any proposed solution $(S_0)$ is guaranteed to be polynomial size w.r.t. $A$. Now, consider a fixed set of $K$ properties $\{k_0, k_1,...k_c\}$, where each property is $coNP-Complete$.

For any solution $S_0$ is considered a valid solution iff: "None of the property in $K$ has a $NO$ instance for $S_0$".

Example: For some hypothetical problem $(A')$ let the solution $S_0'$ be a simple graph with $n$ nodes. Let $k_i$ be the property: "$S_0'$ does not contain a clique with $n/4$ nodes".

Query: Assuming the highly improbable scenario that $P=NP$, it implies $P=NP=co-NP)$. Thus, all the properties in $K$ are $P-Complete$. Does that imply that finding the solution $(S_0)$ for $(A)$ is in $P$ ? It seems so but still need confirmation.

$\endgroup$

1 Answer 1

3
$\begingroup$

Your problem is essentially a $NP^{coNP}$ problem. If $P=NP$ then the polynomial hierarchy collapses and your problem is in $P$.

If $P=NP=coNP$ then we can check in polynomial time whether a solution $S_0$ is valid (using a polynomial-time algorithm to check each property, which exists because $coNP=P$). Thus, the problem is in $NP$, and thus, in $P$.

$\endgroup$
1
  • $\begingroup$ thank you for confirming/clarifying. $\endgroup$ May 26, 2019 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.