# Questions tagged [p-np]

Used for questions about the P versus NP problem.

25 questions
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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. ...
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?
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 ...
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 ...
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 ...