Linked Questions

2
votes
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}$?
2
votes
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 ...
2
votes
1answer
139 views

Proof of NP-completeness via extra information

I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$. I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \...
-2
votes
2answers
111 views

Does NP-hard problems have to be decision problems? (What the fact please) (contradicting answers)

Let me explain my trouble by another example. The wiki page says that Lattice problems are an example of NP-hard problems However, by clicking NP-hard, i find this definition A decision problem H ...
0
votes
0answers
20 views

Does having a similar constraint while reducing a problem to similar problem to prove np hard means they are same?

I have been trying to find the computational complexity of my optimization problem and found that it is Np-Hard. To prove it to Np-Hard, I try reducing it Nurse Scheduling Problem. I am quite confused ...
2
votes
2answers
50 views

Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem

I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following: There exists a believed-today NP-hard problem ...
0
votes
1answer
85 views

Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?

This relates to an answer for this question. The opinion said that: Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most ...
1
vote
0answers
25 views

are all problems in P in NP [duplicate]

I know this is a similar question to this post, but I want to further clarify my understanding. In the picture from wikipedia: I understand that every problem that's in $P$ is also in NP. does this ...
-1
votes
3answers
276 views

Why don't passwords prove P != NP?

Pardon my ignorance on the matter but, Verifying passwords = Polynomial (linear) Guessing passwords = Exponential Since each guess has nothing to do with one another, exponential time is best possible ...
2
votes
2answers
357 views

P vs NP and Angle Trisection (serious question)

I have a question. Please be nice; I come from the corporate world and my knowledge of computer theory is around a college freshman level. My understanding from many popular-level sources (like Scott ...
0
votes
2answers
99 views

Is P contained in NP-hard?

I'm studying complexity classes and the diagram in NP-Hardness article is confusing to me. NP-hard has all problems that can be reduced in polynomial time from a problem in NP to them. P is contained ...
1
vote
1answer
80 views

Reframing decision, counting, enumeration, and search as optimization

The top accepted answers to the questions below allude to two complexity classes of optimization problems: NPO and PO (in relation to NP and P for decision problems): Decision problems vs "real" ...
0
votes
0answers
64 views

Is $k$-Clique NP-hard? [duplicate]

On my lecture note it was written that "Finding a clique of size $k$ in a graph is NP". Later in an example for reduction the following was written: "Assume we know how to answer "Is there a clique ...
2
votes
1answer
147 views

Are problems in NP $\cap$ coNP less difficult than those in NP-complete?

I am taking a complexity class now, and I struggle to understand the concept of "hardness": Assume that $L \in \textsf{NP } \cap \textsf{coNP}$. In means that under the assumption $\mathsf{NP} \neq \...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
3
votes
1answer
78 views

Why isn't DIV necessarily in P? [duplicate]

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\...
2
votes
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 ...
0
votes
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?
0
votes
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?
-1
votes
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}$?
-1
votes
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 ...
1
vote
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 ...
3
votes
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\...
0
votes
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?
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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, ...
1
vote
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 ...
0
votes
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 ...
3
votes
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;...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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$) ...
1
vote
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) ...
2
votes
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 ...
1
vote
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) ...
2
votes
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 ...
0
votes
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 ...
1
vote
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