# Tagged Questions

The tag has no usage guidance.

107 views

### Is there a philosophical counterpart question to P != NP?

Gödels motivation to prove his incompleteness theorems was the philosophical statement "This sentence is wrong.". Is there a philosophical counterpart to the statement P != NP? For example such ...
71 views

### What is the simplest known NP-Complete problem for testing P=NP solutions? [closed]

About a year and a half ago I ask this question regarding $P=NP$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic. With that stated, ...
2k views

### Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?

Basic sanity check on NP-complete solutions: Suppose there was a polynomial time solution for an NP-complete problem, but the size of NP-complete problems that could be solved is still relatively ...
125 views

### How to use an old SAT solver to discover a new one, as is done in The Golden Ticket?

In Lance Fortnow's book The Golden Ticket, he mentions that once you have a polynomial-time algorithm for an NP-complete problem, you can use it to find a faster algorithm. Can you tell me how that is ...
86 views

49 views

### Is anything known about the structure of sets of valuations representable by 3CNF formulas?

Let's suppose we have propositional variables $x_1 ... x_n$. A valuation is an assignment $v$ s.t. $v(x_i)$ is an element of $\{false, true\}$ for $1 \leq i \leq n$. So, there are $2^n$ possible ...
3k views

### Would proving P≠NP be harder than proving P=NP?

Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP. Let Q be one of known NP-hard problems. To prove P=NP, we need to design a single polynomial time algorithm A for Q and prove ...
36 views

215 views

### Why is this argument for $P\neq NP$ wrong?

I know its silly, but i managed to confuse myself and i need help settling this Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some ...
5k views

### What would be the real-world implications of a constructive $P=NP$ proof?

I have a high-level understanding of the $P=NP$ problem and I understand that if it were absolutely "proven" to be true with a provided solution, it would open the door for solving numerous problems ...
991 views

### If P = NP, why does P = NP = NP-Complete? [duplicate]

If P = NP, why does P = NP also then equal NP-Complete? I.e. Why would it then be the case that ...
1k views

### How is it valid to use oracles in mathematical arguments?

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...
143 views

I know that the general consensus among CS researchers is that non-relativizing techniques will be needed to separate P and NP. However, if there is an oracle language $A \in \textbf{P}$ such that ${\... 1answer 81 views ### What is the implication of the sentence: “if any NP complete problem is p time solvable, then all problems in NP are p time solvable” I find this quote here on page 13 Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p ... 1answer 420 views ### Subset sum algorithm in O(n³ log n)? I think that I have found an algorithm which resolve exactly the subset sum problem in$O(N^3)$in the worst case, only for positive numbers. After my research, I'm lost between all the algorithms ... 1answer 201 views ### If one shows that UNIQUE k-SAT is in P, does it imply P=NP? Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the ... 1answer 210 views ### Homomorphism erasing information I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under ... 1answer 113 views ### Problem with my proof that NP = coNP? Is there a problem with this proof that NP = coNP? It suffices to show that Satisfiability can be solved efficiently with at most a polynomial number of queries to an oracle for Tautology. The ... 1answer 103 views ### What are the current known implications of the complexity of Integer Factorization? According to my limited knowledge we know that since Integer Factorization lies in the intersection of NP and co-NP it cannot be NP-complete unless NP=co-NP. However, do we know any other ... 2answers 110 views ### What happens to quantum algorithms such as BB84 if P=NP Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible). The BB84 algorithm is based on the idea that by observing a quantum state, one has to (... 1answer 77 views ### A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP Wikipedia states on sparse languages that There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP$\subseteq$... 2answers 238 views ### Does this mean$P = NP\$

I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser's "Theory of Computation" (2013 ...