# Questions tagged [p-np]

Used for questions about the P versus NP problem.

**0**

votes

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**2**answers

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

**3**answers

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

**2**answers

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

**1**answer

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

**2**answers

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

**4**answers

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

**6**answers

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

**5**answers

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

**2**answers

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

**7**answers

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

**1**answer

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

**7**answers

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

**15**answers

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

**6**answers

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