# Tagged Questions

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!
43 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? ...
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 ...
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 ...
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 ...
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 ...
417 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 ...
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 ...
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 ...
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 ...
238 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 ...
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 ...
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 ...
618 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 ...
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 ...
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 ...
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) ...
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 ...
789 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 ...
206 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 ...
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 ...
7k 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!
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: ...
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 ...
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 ...
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$ ...
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 ...
869 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 ...
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 ...
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 ...
479 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 ...
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 ...
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 ...
969 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 ...
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 ...
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 ...
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$ ...
191 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 ...
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 ...
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 ...
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 ...