Questions tagged [p-np]

Used for questions about the P versus NP problem.

0
votes
0answers
20 views

Cook's theorem and NP complete reductions

Based on Cook's theorem, Any NP problem can be converted to SAT in polynomial time I know that SAT is a NP-complete problem. Therefore, is it accurate to say: If we can reduce a search problem A (...
-3
votes
1answer
66 views

Sharepoint PNP For Developer

I work on SharePoint programming. I recently became acquainted with a topic called Sharepoin Pnp . What is the nature of sharepoint pnp? When should it be used? What is the connection with Web Part ...
0
votes
1answer
75 views

P equals NP description is easy

In the official link of the P=NP problem at the below page: P=NP Problem Official Description , there is mentioned a problem of organizing housing accommodations for a group of four hundred ...
-1
votes
1answer
30 views

What are the examples of NP problems that is reducible to a NP-complete but not the other way round?

What are the examples of NP problems that is reducible to NP-complete problem but not the other way round? When I read about NP and NP-complete, I thought the mapping will be one-one such that it is ...
0
votes
2answers
66 views

How to pick only 4 set of integers from a set in polynomial time algorithm

The whole thing about this polynomial time is confusing to me for example: I want to write a program in a polynomial time algorithm that will just pick only 4 integers that sum to 0 from a set. For ...
0
votes
1answer
180 views

Definition of NP Complete

I'm trying to understand the formal definition of NP Complete and had some questions. I was wondering if someone can provide more insight. The Jon Kleinberg algorithms book says that if every NP ...
1
vote
1answer
483 views

Reduction of A to B : True or False

There are two statements: If a decision problem A is polynomial-time reducible to a decision problem B (i.e., A≤ pB ), and B is NP-complete, then A must be NP-complete. And: If a decision problem B ...
1
vote
1answer
577 views

3SAT solving though DNF simplification?

I have thought of an algorithm to solve 3SAT problem via the below approach : 1) Take all the clauses in the cnf equation who have at least one variable in common. Find all such combinations and put ...
0
votes
1answer
334 views

I have found on the Internet polynomial time algorithm for graph coloring, possibly proving P=NP

I was searching for graph coloring algorithms, and I have found algorithm, which, how author states, runs in polynomial time. Author gives also C++ program source code and demonstration program. The ...
0
votes
1answer
745 views

3SAT solved in polynomial time?

I have seen few errors in the cnf files for both satisfiable and unsatisfiable clauses files SATLIB Benchmark Problems To be more specific I have found out that the 1st file of the zip folder here: ...
2
votes
1answer
132 views

Primes in P - what about running till the sqrt?

I'm learning about P and NP. I've read that the problem of deciding if a given number is prime is a problem in P, which means that it has a polynomial-time algorithm which solves it. I've also read ...
0
votes
2answers
2k views

Opencv : Solve PNP error, EPNP and P3P failed

I'm trying to compare precision and time consuming between every SolvePnP possibility : CV_ITERATIVE, CV_EPNP, and CV_P3P I also compared my result with Matlab EPNP. And it's look like EPNP and P3P ...
3
votes
3answers
261 views

P-NP problems solved? FindBugs solves the halting prob?

There is a tool called FindBugs it can detect infinite never ending loops in a given program/ code base. This implies FindBugs can detect if a program will end or not by analyzing the code. Halting ...
2
votes
2answers
294 views

Would an exponential lower bound on an NP-complete language prove P does not equal NP?

If someone were able to prove an exponential lower bound for a NP-complete problem, would that prove that P ≠ NP?
-1
votes
1answer
24 views

Project Suggestions for a Complexity Class

I'm taking a 400-level class on Complexity and Problem Solving. The final project is to implement a problem that has to do with P and NP. Unfortunately, the teacher has been inexcusably vague about ...
2
votes
2answers
4k views

can some sorting be P, NP, and NP-Complete?

I am quite confused, and this is my thought after some reading: P is in NP and NP is in NP-Complete. Therefore, all P could be in NP and NP-Complete? Does that mean there are sorting algorithms ...
9
votes
4answers
2k views

“Finding all the code in a given binary is equivalent to the Halting problem.” Really?

Was just reading the highly voted question regarding Emulators and the statement It's been proven that finding all the code in a given binary is equivalent to the Halting problem. Really ...
26
votes
6answers
17k views

NP-hard problems that are not NP-complete are harder?

From my understanding, all NP-complete problems are NP-hard but some NP-hard problems are known not to be NP-complete, and NP-hard problems are at least as hard as NP-complete problems. Is that mean ...
16
votes
5answers
3k views

Why are NP problems called that way (and NP-hard and NP-complete)?

Really.. I'm having the last test for graduation this Tuesday, and that's one of the things I just never could understand. I realize that a solution for NP problem can be verfied in polynomial time. ...
2
votes
2answers
881 views

What are NP problems?

I read the article on wikipedia but could not understand what exactly are NP problems. Can anyone tell me about them and also what is relation of them with P Problems?
66
votes
7answers
17k views

Explain the proof by Vinay Deolalikar that P != NP [closed]

Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP. Could someone explain how this proof works for us less mathematically ...
8
votes
1answer
420 views

P=NP: What are the most promising methods?

I know that P=NP has not been solved up to now, but can anybody tell me something about the following: What are currently the most promising mathematical / computer scientific methods that could be ...
9
votes
7answers
1k views

What is missing for this P != NP proof?

I tried to recover a password. When thinking of this I recognized that the problem "password recovery" is a very nice example of a NP problem. If you know the password it's very easy to verify it in ...
17
votes
15answers
4k views

What would a P=NP proof be like, hypothetically?

Would it be an polynomial time algorithm to a specific NP-complete problem, or just abstract reasonings that demonstrate solutions to NP-complete problems exist? It seems that the a specific algoithm ...
216
votes
6answers
81k views

What's “P=NP?”, and why is it such a famous question? [closed]

The question of whether P=NP is perhaps the most famous in all of Computer Science. What does it mean? And why is it so interesting? Oh, and for extra credit, please post a proof of the statement's ...

http://mssss.yulina-kosm.ru