1
vote
1answer
25 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
1
vote
1answer
44 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
1
vote
2answers
92 views

Which pure mathematical problems could be tackled with an algorithm solving NP-complete problems?

In the past, practical applications have motivated the development of mathematical theories, which then became the subject of study in pure mathematics, where mathematics is developed primarily for ...
10
votes
1answer
166 views

Is it possible that P != NP cannot be proved?

I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
5
votes
2answers
202 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
3
votes
2answers
169 views

Simple problem whose approximation ratio is still open.

I am preparing for a talk on "Approximation Algorithms", aimed at undergraduate students. In order to motivate the topic, I want to give them an example of a problem which is easy to describe and has ...
-3
votes
1answer
418 views

Is solving the PvsNP example question a solution to PvsNP?

This example question was created by the claymath institute. The PvsNP question states, suppose the dean leaves you with a task to house a group of 400 students inside dorms. But there is only enough ...
-4
votes
1answer
195 views

How does 3-sat work in laymen's terms?

I know only basic math like so: (+,-,x,\,). And I studied a little bit of programming up to the point of knowing a little bit about Boolean values.I desperately want to understand the 3-sat question ...
0
votes
0answers
62 views

Please explain the unsolved 3-sat math problem as easy as possible for someone with only basic math skills [duplicate]

I know only basic math like so: (+,-,x,\,). And I know a little bit of programming up to the point of Boolean values.I desperately want to understand the 3-sat question fully so I can solve it, but ...
1
vote
1answer
250 views

I don't understand the proof for reducing Subset-Sum to Scheduling with release time.

I found this proof for showing that Scheduling with Release Time is NP-Hard by reduction to Subset-sum, but I don't understand it: Scheduling With Release Time: Given a set of $n$ jobs with ...
0
votes
1answer
239 views

Integer Linear Programming (ILP): NP-hard vs. NP-complete?

I was thinking about examples where a problem is NP-hard but was not NP-complete and ILP came to mind. It is obviously NP-hard but is it NP-complete? I.e., is it in NP? Given a certificate (the ...
3
votes
2answers
72 views

why is it necessary to show NP in order to show NPC?

I am reading Introduction to Algorithms 3rd for my CS course. Lemma 34.8 says to prove a language $L_2$ NP-complete: If $L_2$ is a language such that $L_1 \le_P L_2$ for some $L_1 \in$ NPC, then ...
5
votes
2answers
166 views

Why does input size matter in NP theory?

When my prof introduced us to the N/NP topics, the first thing he mentioned is input size, which he defines as the number of bytes needed to describe and write a problem's input into a file. Could ...
9
votes
2answers
620 views

Two $NP$-complete languages whose union is in $P$?

I've been thinking about transformations on $NP$-complete problems that produce languages known to be in $P$. However, I can't seem to find an example of two $NP$-complete languages whose union is in ...
1
vote
0answers
265 views

Polynomial-Time reduction: Clique Problem

Here is an exercise my friend proposed to me: Show that the maximum clique problem polynomial time reduces to the maximum independent set problem. Here is my attempt at solving it: It is known ...
0
votes
1answer
403 views

NP-Completeness of Certain Bounded Degree Graphs

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems. 1) L = set of all (G, k) where G is a graph with ...
1
vote
2answers
573 views

P or NP-Complete? (concerning 2-CNF formulas)

I have two languages that I want to either prove is in P or NP-complete. 1) 2-CNF formulas where there exists an assignment that satisfies the 3/4 of the first 1000 clauses and all of the rest. 2) ...
3
votes
1answer
229 views

Proving NP-completeness intuition

When approaching a problem in NP, initially not knowing whether the problem is in P or NP-complete (or some other choice). It seems to me the only way one can go about "solving" this problem is to ...
5
votes
2answers
793 views

Why is integer factorization considered to be in NP if a quantum computer can compute a factorization in polynomial time?

Sorry if this seems off topic, the cstheory guys told me it was off topic over there, and sent me here. Shor's algorithm on a quantum computer can solve an integer factorization problem in polynomial ...
1
vote
2answers
207 views

Is Turing completeness monotone with respect to Cook reductions?

I think the post title is relatively clear assuming I worded it correctly, but since I was thinking of a specific example: The language of Boolean expressions is Turing complete; Does this imply that ...
1
vote
2answers
381 views

Check Whether A Boolean Formula Has One Satisfying Assignment

So I'm reviewing old homeworks for an upcoming comp sci test and I came across this question: Say whether the following statement is True, False or Unknown: The problem of checking whether a ...
4
votes
2answers
8k views

What is the 3SAT problem?

I don't get the 3SAT problem. Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples? Thanks!
0
votes
1answer
487 views

Is this partition problem strongly NP-complete?

The Partition problem is weakly NP-complete: Given a set A of positive integers, can A be partitioned into two disjoint subsets with the same sum? I'm interested in the hardness of this variant: ...
2
votes
2answers
1k views

Is coNP closed under Kleene star?

Is coNP closed under Kleene star operation? I have the answers, in which they say it is possible to build a graph that describes all possible divisions of the string in which the sub-words are in in ...
0
votes
1answer
74 views

inapproximability within $1+n^{\epsilon}$

I am a bit confused with the notation of an optimization problem not being approximable within a factor of $(1+n^{\epsilon})$. What exactly does this mean? I am confused because if I (as a user of ...
2
votes
3answers
460 views

Fake Proof that $\mathrm{NP}^\mathrm{NP} = \mathrm{NP}$

I found this faulty proof of $$ \newcommand{\NP}{\mathrm{NP}} \NP = \NP^{\NP}, $$ where the tricky part is to proof that $ \NP ^{\NP} \subseteq \NP$, and this is how it is realized: Take $\NP^\NP$ ...
1
vote
1answer
137 views

Reduction over intersection of languages

Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$. 1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to ...
1
vote
1answer
873 views

crack RSA: NP, or NP-complete?

I've heard differing opinions/statements of fact from different professors and sources as to whether cracking RSA is "thought" to be in NP, or known to be an NP-complete problem. Can anyone shed light ...
5
votes
2answers
772 views

Subset sum problem is NP-complete?

If I know correctly, subset sum problem is NP-complete. Here you have an array of n integers and you are given a target sum t, you have to return the numbers from the array which can sum up to the ...
4
votes
2answers
176 views

How do we know if a problem is hardest in NP

I read that the definition of NP-complete is : These are the hardest problems in NP. Such a problem is NP-hard and in NP How do we know if a problem is hardest in NP, and no harder problem ...
4
votes
3answers
480 views

NP hard/complete

I have never been very clear on this concept. Please help: At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have ...
32
votes
6answers
2k views

Simple “real life” NP-hard problems?

There are many proofs lying around that games like Lemmings or Sudoku or Tetris are NP-hard (generalized version of those games, of course). The proofs, as I recall, are not difficult but not simple ...
4
votes
3answers
1k views

Proof Hampath is NP-Complete

I'm really confused by the proof that Hampath is NP-Complete. In order to prove something is NP-Complete, we can reduce another NP-Complete problem to it. So we want to take 3-SAT and reduce it to ...
16
votes
2answers
970 views

What is the complexity of succinct (binary) Nurikabe?

Nurikabe is a constraint-based grid-filling puzzle, loosely similar to Minesweeper/Nonograms; numbers are placed on a grid to be filled with on/off values for each cell, with each number indicating a ...
8
votes
3answers
625 views

NP vs NP-Complete

Is there any problem which is in NP but not in NP-Complete? Is there any possibility that this problem is analogous to P=NP problem, if so is there any problem which is in NP, but currently there is ...
4
votes
2answers
162 views

Many one and One many reductions

I do not have enough complexity theory background, but I was wondering about the kind of reductions that we normally do to show NP-Completeness. I think all of the reductions that I have seen are ...
1
vote
1answer
435 views

Independent Set decision problem in P

If P=NP, is there a polynomial-time algorithm $A$ that can decide the $\text{Independent Set}$ decision problem? That is, with an undirected graph $G = (V, E)$ and a positive integer $k$, does $G$ ...
3
votes
1answer
192 views

The Hamiltonian problem on Polyominoes

A polyomino is a connected subset of $\mathbb{Z}^2$ - a set of squares joined along their edges such that the resulting form is connected (or, more shortly, a generalized form of Tetris cube). A ...
5
votes
2answers
321 views

Question about the P versus NP Problem

It seems to be an accepted belief based on decades of experience that naive algorithms are not adequate to solve NP-complete problems in a reasonable amount of time. Even those who believe P = NP ...
11
votes
1answer
487 views

Assuming $P \neq NP$, do we know whether there are problems which are in $NP$, not in $P$ and are not $NP$ complete?

Here's a question. Have there been any theoretical results showing that if $P \neq NP$, there must exist some problems in $NP$ which are not $NP$-complete and which are not in $P$ either? Just ...
12
votes
6answers
3k views

The Practical Implication of P vs NP Problem

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it. Suppose that we can prove all questions that can be ...
13
votes
3answers
4k views

What are NP-complete problems and why are they so important?

I keep hearing questions about whether something is NP-complete, but they never really mention what it is. Why do people care so much about NP-complete problems?