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}$?
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 ...
139 views

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