# Linked Questions

3answers
565 views

### Are there problems in NP that do not reduce in polynomial time to any problem in NP?

As the title says: are there problems in $\mathbf{NP}$ that do not reduce in polynomial time to any problem in $\mathbf{NP}$?
2answers
140 views

### determine Eulerian or Hamiltonian

I am a beginner in graph theory and just found this question in a book after completing few topics and I was wondering how you approach this questions. For eulerian, I can say that the graph has ...
1answer
139 views

0answers
18 views

### Proving a problem is NP [duplicate]

I've seen in many textbooks if say we have a problem $Q$, we write a non-deterministic algorithm in polynomial time to solve problem $Q$, and then from that point it results that $Q\in NP$. Why is ...
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 ...
1answer
40 views

### What are the differences between NP-Complete and NP-Hard? [duplicate]

What are the differences between NP, NP-Complete and NP-Hard? I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what's ...
2answers
212 views

### How to prove NP-hardness from scratch?

I am working on a problem of whose complexity is unknown. By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use. Finally, I have decided ...
2answers
490 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 ...
1answer
446 views

### What's the purpose of the non-deterministic Turing machine?

(*) Acronyms NTDM := non-deterministic Turing machine. TM := deterministic Turing machine. (*) Consider the following idea The NTDM is able to follow, in parallel, all paths of the tree of the ...
1answer
168 views

### Pseudo-Proof of Constrained Sudoku is co-np

The definition of CO-NP A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. In other words, co-NP is the class of problems for which there ...
1answer
78 views

In my formal languages class, we discussed DIV, defined as following: $\mathrm{DIV} = \{\langle a,b\rangle : \text{$a, b \in N$and$a$has a divisor$d$for some$1 < d \leq b$}\}$ ($\langle\... 2answers 623 views ### Proof that POSITIVE-3-SAT is in the complexity class P I have the following language: $$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable boolean formula in conjunctive normal form,}\\ \text{ in which all clauses consist of ... 0answers 32 views ### Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? [duplicate] Where f(n) = n! belongs to? P, co-P, NPComplete or NPHard? 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? 1answer 44 views ### Why does L\subseteq \textbf{P} \cap \textbf{NP} is \textbf{NP}-complete imply \textbf{NP} = \textbf{P}? [duplicate] If I show that a language L is contained in \textbf{P} and \textbf{NP} and I know that the language is \textbf{NP}-complete, why did I proof that \textbf{P} = \textbf{NP}? 1answer 58 views ### Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate] Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how ... 0answers 11 views ### Proof/certificate in a decision problem? [duplicate] In this wikipedia article, the following comment is made: Consider an arbitrary decision problem in the class NP. By definition each problem instance x which are answered 'yes' have a certificate ... 1answer 1k views ### Verifier - Complexity Theory A Verifier for a language A is an algorithm V such that$$A=\left\{ w \space | V \space \text{accepts} \space \langle w,c\rangle \space\text{for}\space \text{some} \space \text{string} \space c\... 0answers 37 views ### Prove the language L of all palindromes over {0,1} is in NP Wouldn't this language be in P, since it is a context free language. And every context free language is a member of P? Or would it be otherwise? 1answer 392 views ### Is it immediately true that the class of P is a subset of the class NP? [duplicate] Forgive me if this is a stupid question - it's been a while since I thought at all about complexity theory and I want to make sure that I have covered all the possible angles with regards to the ... 0answers 21 views ### NP hardness - Why is one harder than the other? [duplicate] As far as my understanding goes, to show that a problem A is NP-hard, we use another NP-complete problem B. We reduce (in polynomial time) from B to A, i.e. use A to solve B. This shows that A is ... 1answer 69 views ### Reducible and NP Hard [duplicate] I have been confusing a bit about these relationship: Given A polynomial reducible to B 1/ If A is NP hard, what is the hardness of B? 2/ If B is NP hard, what is the hardness of A? 3/ If A has ... 0answers 97 views ### Proving P and NP on problems formulated as languages To prove that a certain problem is in P we have to give an algorithm that decides or solves it in polynomial time. To prove that a problem is in NP an algorithm must exist so that it can check whether ... 1answer 71 views ### What is the difference between exactness and optimality of an algorithm? I'm studying some papers related to graph partitioning (GP). It is well-known that the GP problem is NP-Complete. Based on my understanding, it means that there is no polynomial time solution to solve ... 0answers 25 views ### NP-Hard for resolving P=NP [duplicate] Im studing complexity theory and im reading this question on Quora. According to what the guy is saying : if we are able to solve a NP-Hard problem in polynomial time we have prooved that P=NP. But, ... 0answers 51 views ### Finite State Machine trasition possibilities Im studying finite state machines, in particular the deterministic and the non-deterministic versions. What i have not understood is : why in a non-deterministic state machine it's allowed that ... 2answers 540 views ### Definition of NP [duplicate] We know that NP is the class of languages recognized by a nondeterministic Turing machine (NTM) in polynomial time. I've also read that NP is the class of problems can be solved by NTM in polynomial ... 0answers 786 views ### Does NP-hard problems have to be decision problems? [duplicate] According to the selected answer on this question NP-hard problems do NOT have to be decision problem. But by definition all NP-hard problems can be karp-reduced from any NP-problem in polynomial time;... 2answers 85 views ### Isn't NP problems always also co-NP problems? I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every ... 1answer 1k views ### What is meant by problems not in NP but in NP hard? [duplicate] If there is a proof that an NP-Hard problem which is not NP-Complete can be solved in P time, it does say that the verification time is polynomial too. Why doesn't it then mean that all NP-Hard are ... 1answer 51 views ### Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP? [duplicate] I only just recently learned about the P=NP problem in introduction to algorithms class, and I'm still trying to wrap my head around it. I thought of this situation while cleaning my room today and ... 1answer 67 views ### P versus NP and what we are looking for [duplicate] I was reading the other day about this problem, refreshing it, and on a couple of places over the internet I read somebody explaining something in the line of '..does not matter as long as is ... 2answers 423 views ### Show that boring boolean circuit belongs to NP-complete class We say that a boolean circuit is boring if it returns the same result for$>\frac34$possible input, where we have$n$input gates. Hence, boring circuit returns the same output ($0$or$1$) ... 2answers 152 views ### complexity theory NP [duplicate] Ok, I really need help because I have read in so many books but still don't understand the complexity class NP. These are the books: Theoretische Informatik; Katrin Erk, Lutz Priese (german) ... 1answer 1k views ### Question about NP problem certificates and P=NP From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate. My ... 1answer 98 views ### Clarification of definition of class$DisNP$I an trying to learn about$DisNP$Complexity class. I couldn't find this class in any book. But, regarding it, I found this definition in a paper: Definition: A disjoint NP-pair (NP-pair for short) ... 1answer 3k views ### Does NP mean verifiable in polynomial time or solvable in polynomial time? [duplicate] Is NP defined as verifiable in polynomial time, or solvable in polynomial time? Verifiable meaning that the solution can be checked in polynomial time, and solvable meaning that the solution can be ... 0answers 34 views ### Why some state that Primes is in NP? [duplicate] Why some books state that Primes is a NP problem if, as a decidibility problem, it can be solved in polynomial time? A simple example: A number can has its primality tested by dividing it by all ... 3answers 536 views ### Bounds in NP-completeness proofs According to the polynomial-time-reduction definition "If problem$Y$can be reduced to problem$X$in polynomial time, we denote this by$Y \leq_p X$." If$X\$ is one of already known NP-complete ...

15 30 50 per page