Questions tagged [p-vs-np]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
23 views

Any computational problems used to develop vaccines? [closed]

I have a deep understanding of the P vs NP question, and how unlikely they are. However, i want to know if they are, what computational problems(np-problems) can help develop a vaccine (i.e. for ...
0
votes
3answers
35 views

Is it possible that Co-NP = P but NP != P

Suppose there exists an algorithm that takes as input an unsatisfiable SAT formula, and never fails to verify it in polynomial time. However, when the input is a satisfiable formula, it doesn't work (...
1
vote
1answer
53 views

P=NP when number of inputs that give 1 is bounded by polynomial

Suppose there exists some NP-complete problem such that the number of inputs that gives 1 as an output is bounded by a polynomial; that is, if the problem is $f \colon \{0, 1 \}^* \to \{0, 1\}$, then, ...
0
votes
1answer
306 views

Prove or disprove, If A ≤p B and B is NP-hard, then A is in NP-hard

Intuitively if A can reduce to B, and B is NP-Hard, A might be NP Hard but maybe not. If there is a way to solve A that does not involve reducing to B, it might be faster. How do I formally disprove ...
0
votes
1answer
77 views

Prove or Disprove, 3SAT ≤p 2SAT, then P = NP

I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.
1
vote
1answer
38 views

Can you apply neural networks to design algorithms?

I’m kind of a newbie to neural networks (and CS in general) but I was wondering if there are any methods to apply them in such a way with the aim of producing algorithms that solve difficult math ...
2
votes
2answers
348 views

P vs NP and Angle Trisection (serious question)

I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level. My understanding from many popular-level sources (like Scott ...
0
votes
0answers
24 views

How sub-exponential time does $\text{3SAT}$ have to be to make $\text{NP} \neq\text{EXP}$? What else would imply $\text{NP} \neq\text{EXP}$?

The exponential-time hypothesis posits that if $\mathsf{3SAT}$ has NO subexponential time algorithm (i.e. one in $\mathcal O(2^{o(n)})$), then $\mathsf{P}\neq \mathsf{NP}$. However, I am interested ...
268
votes
7answers
126k views

What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
2
votes
1answer
199 views

Would a sparse NP-Complete language imply L = NP?

Would a sparse NP-Complete language imply L = NP? Update: Thanks to Noah Schweber for clear and comprehensive answer. Having thought about it more, one would need a logspace reduction from NP-...
7
votes
1answer
856 views

Algorithms that run in polynomial time if P=NP

On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking ...
0
votes
1answer
27 views

If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?

Deciding bipartite hypergraph coloring is NP-hard: While for bipartite graphs a 2-coloring can be found in linear time, it was shown by Lovasz [10] that the problem to decide whether a given k-...
2
votes
1answer
61 views

How to know if a problem belongs to NP Class?

What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we ...
5
votes
1answer
201 views

P vs. NP and Godel's Theorems

This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct. Basically, I'm wondering if it is plausible for there to be a formal proof ...
1
vote
1answer
63 views

Time complexities of state-of-the-art SAT solvers with respect to length of the formula

I am learning about DPLL and CDCL SAT solvers, and I know that they have time complexity exponential to the number of variables. If I am not mistaken, one of the reasons why most believe P does not ...
1
vote
3answers
52 views

NP-complete problem 3-SAT, is there a difference in complexity between just providing yes/no without exact solution

The 3-SAT problem is NP-complete, meaning that no known algorithm can provide an exact solution in polynomial time, while a solution can be tested very quickly in polynomial time. My question is, ...
-1
votes
1answer
119 views

Showing on-line P = NP

I have developed a theorem that proposes a method to build algorithms. All the algorithms produced by this method are in P ... they never go up to more than $6(n^{12})$ operations. Following that, I ...
24
votes
5answers
7k views

P = NP clarification

Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example. My understanding of P=NP question is that, given the optimal solution of a difficult problem,...
1
vote
1answer
2k views

A problem in NP but not NP-complete?

Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.
0
votes
1answer
32 views

how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
7
votes
3answers
806 views

What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

Here we see a very interesting attempt to show that $\mathrm{P} \ne \mathrm{NP}$ by Norbert Blum. Here we see 116 previous attempts at solving P vs. NP. Here we see the P vs NP problem defined as: ...
4
votes
2answers
2k views

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

About a year and a half ago I asked this question regarding $\mathsf{P}=\mathsf{NP}$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic....
0
votes
1answer
86 views

P Vs NP can never be proven one way or the other!

Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem. And since if we prove that any problem in NP is a P that would mean that we have NP=P. ...
4
votes
3answers
2k views

If a problem is in P solved via dynamic programming, is it also in NP?

So I can solve a given problem using dynamic programming in $O(n^2k^2)$ time complexity. This means that the problem is in P. But I am asked if it is in NP. My answer is, "Since it is also polynomial ...
0
votes
1answer
47 views

Does computational complexity theory take into account problems with subjectivity in the verification of a solution?

When we discuss P vs NP we are looking at the difference between problems that are easily solved versus easily verified (wrt polynomial vs exponential time). But in both cases these are black-and-...
2
votes
2answers
266 views

What's the flaw in the P != NP proof in the article “The Computational Complexity of the Traveling Salesman Problem”

I am reading through some proof of inequality of P and NP but they are not accompanied by the flaws in the reasoning so I'm trying to find them by myself, just to see if I'm getting the logic right. ...
0
votes
1answer
309 views

How to prove Exact cover problem is NP Complete using Vertex Cover problem?

Using reduction theorem in NP, we want to prove that Exact cover is NPC by reducing it from Vertex Cover Problem. It is easy to derive it from SAT, but we can't find a solution yet to derive it from ...
0
votes
1answer
120 views

Is this statement of P = NP in Agda correct?

Looking for a self-contained statement of P = NP in type theory, I stumbled upon this short Agda formalization (a cleaned up version is reproduced below). The statement here does seem to express the ...
1
vote
0answers
36 views

Weaker conjectures to prove in order to arrive at P =/= NP

We know we have a long way to go before we come to a proof of P $\neq$ NP. We also know that this road is studded with minor conjectures that will have to be proved/disproved in order to arrive at the ...
-4
votes
1answer
216 views

Is it possible that P vs NP is not the real problem?

Lets assume that I found a polynomial solution for Hamiltonian path problem. It is known that you can reduce this problem to SAT. How ever it will be a special case of SAT. Just the case where there ...
10
votes
4answers
5k views

Evolving artificial neural networks for solving NP problems

I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. ...
2
votes
1answer
58 views

How is $\text{PCP}[O(\log n),O(1)]$ NOT P?

As a prover, we just try to convince the verifier that it's correct, no matter whether it is or not. So we can just analyze every possible route. For $\text{PCP}[O(\log n),O(1)]$, won't there just be ...
18
votes
7answers
4k 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 ...
0
votes
0answers
43 views

Confusion about P versus NP [duplicate]

I'm sure that in my following question my reasoning is extremely simplistic and flawed, but I think if someone answered this it would help me understand what the P vs NP conundrum is. So here is my ...
1
vote
2answers
273 views

P/NP - Polynomial Reduction vs Certificate

I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate. How I understand polynomial reduction is that you can use it to ...
0
votes
1answer
174 views

Baker, Gill, Solovay - construction of oracle B such that P^B != NP^B

I have some questions about Baker, Gill, Solovay proof of the existence of an oracle such that P^B != NP^B. The proof can be found in Siam Journal of Computing, 4:432-442, 1975 [219]. Why Isn't this ...
99
votes
5answers
15k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction....
2
votes
1answer
74 views

Doubts about Baker-Gill-Solovay

How am I supposed to read the P=?NP relativization proof? I am reading the classical paper Relativization of the P=?NP problem by Baker, Gill and Solovay, in particular the proof that there exist an ...
2
votes
3answers
130 views

Is the P vs NP problem, an NP or co-NP problem?

A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining P vs NP, in a semi-vulgarized way : https://www.youtube.com/watch?v=YX40hbAHx3s At 7 minutes ...
-1
votes
3answers
475 views

One-way Trapdoor Function

Do the functions of the collatz conjecture and their inverses model a Trapdoor Function? If given a, b, a^-1, b^-1 and your choice of f(x), is it “hard in the average case” to find some secret x? I ...
1
vote
1answer
235 views

P vs NP question from GeeksforGeeks

From here: https://www.geeksforgeeks.org/algorithms-np-complete-question-2/ Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to ...
10
votes
2answers
4k views

Contradiction proof for inequality of P and NP?

I'm trying to argue that N is not equal NP using hierarchy theorems. This is my argument, but when I showed it to our teacher and after deduction, he said that this is problematic where I can't find a ...
2
votes
1answer
115 views

proving that $P\ne NP$ under an assumption

Suppose that $P^{SAT} \not\subseteq coNP$. Prove that $P\ne NP$. What I did: Suppose that $P=NP$. Then, $P = coP = NP = coNP$. We know that $P^P = P$. Then, by assumption: $P^{NP} = NP = coNP$ ...
1
vote
1answer
93 views

A tricky P=NP problem

Define an operator $\pi(\cdot)$: for a language $L$, $\pi (L)$ is the set of all prefixes of strings in $L$ with length at least half of the original string. Prove that if $\mathsf{P}$ is closed under ...
0
votes
0answers
28 views

Reducing SAT to a P problem in polinomial time [duplicate]

Does reducing SAT in polynomial time to a P problem would mean that P = NP?
10
votes
1answer
3k views

If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$?

If $\mathbf{P} = \mathbf{NP}$, then is $\mathbf{L} = \mathbf{NL}$? I am asking this question because, for other non-deterministic classes, it seems $\mathbf{P} = \mathbf{NP}$ always establishes that ...
2
votes
1answer
114 views

What is Ironic complexity? What are some good resources to learn about it?

The term "Ironic complexity" was coined by Scott Aaronson for the stuff Ryan Williams does in the area of complexity theory. Could anyone tell me what kind of problems and approaches does Ryan ...
7
votes
1answer
2k views

If graph isomorphism is in P, is then P = NP?

I think that, since graph isomorphism is not known to be $\textbf{NP}$-complete, we can not reduce all problems in $\textbf{NP}$ to it, and therefore the implication does not hold. Additionally, in ...
1
vote
3answers
4k views

What are the implications of P=NP? [duplicate]

Is there a list of implications of $P=NP$? Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.
0
votes
1answer
42 views

Effective Procedures and P vs NP Problem

If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two ...