# A query regarding P vs NP

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.

## 1 Answer

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

• thank you for confirming/clarifying. May 26, 2019 at 12:32