Linked Questions

0
votes
1answer
491 views

Can someone provide an introductory example of a certificate in complexity theory? [duplicate]

Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept. From my understanding, a certificate is used when you are trying to ...
1
vote
1answer
364 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 ...
3
votes
1answer
203 views

Can someone explain in a simple way what “reducible” mean in complexity theory? [duplicate]

I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value. What does it exactly mean by problem A reducible to B? Does it mean that A can be ...
1
vote
1answer
271 views

How is the complexity of algorithms to solve 3CNF (decision problem) specified? [duplicate]

For k inputs, the complexity of naive algorithm is O(2^k). I understood this one. What is meant by "the size of the instance to be solved should be polynomial in k". Is it equivalent to the statement ...
1
vote
2answers
150 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) ...
-1
votes
1answer
150 views

How do we know that all NP problems reduce to NP-hard problems? [duplicate]

For example, how is it proven that any NP problem can reduce to subset sum, circuit satisfiability, etc.? Or could you link to a proof?
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 ...
0
votes
1answer
101 views

Does classification of a problem also require the algorithm used? [duplicate]

Just learnt that a problem in computer science can be divided into the following categories Polynomial problems NP problems NP hard problems NP complete problems ...
-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}$?
0
votes
0answers
112 views

The defining property of problems in NP [duplicate]

I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some ...
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 ...
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 ...
-1
votes
1answer
55 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 ...
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 ...
1
vote
1answer
43 views

NP-Completeness: A question about reduction and hardness [duplicate]

I am trying to understand the definition / meaning of reduction. Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For ...

15 30 50 per page
1
2
3 4 5
9