1
vote
0answers
32 views

How hard is this constrained $n$-rooks problem?

Suppose you have an ($n \times n$)-chessboard, together with a constraining function $C : n \times n \to 2$ where $C(i,j) = 1$ iff you're allowed to place a rook in the $ij$-square. Consider the ...
1
vote
1answer
17 views

Trying to prove something in complexity

I just started to learn about complexity-theory, and I'm trying to prove this: If P=NP, then every (non-trivial) language in P is NP-complete. Can someone give me a solution please?
1
vote
1answer
70 views

Mixed Q horn SAT

I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ...
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
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? ...
0
votes
2answers
56 views

What does psuedo-polynomial algorithm for subset sum problem mean?

Help me out here - just trying to better understand what 'psuedo-polynomial' means... If the input to an NP-Complete problem is 100 items(ie n=100), and the 'target' is the actual value '100'(t=100): ...
2
votes
1answer
62 views

Prove 2-HamiltonianCycle $\in \textbf{NP}$

Just want to verify that I have the right idea here with this hamiltonian cycle question. $HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
6
votes
1answer
674 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
0
votes
0answers
14 views

In the definition of NP, is it required to have polynomially bounded length of certificate?

So given the definition in our lectures, we were told that NP is defined as the set of languages $L$ s.t. there exist a polynomial time bounded Turing-acceptor M s.t. $L ={w: M accepts(w#c) for some ...
2
votes
2answers
62 views

np or np complete proof of a factory problem

Good evening everyone; I face with this problem and I could not find a way to proof it. Here is the problem; A={Writing out the factorial of a number in unary NP-complete or NP-hard (e.g. n! = 11 ...
1
vote
0answers
39 views

Is Quadratically Constrained Quadratic Program (QCQP) in NP?

The general version of QCQP is NP-hard, but is it also NP-complete? That means, is there a non-deterministic algorithm, which solves QCQP in polynomial time complexity? If the general version of QCQP ...
2
votes
1answer
106 views

Finding no-self-intersecting path in geometric graphs

Is there a polynomial algorithm to determine whether there exists no-self-intersecting path between given vertices $s$ and $t$ in a geometric graph $G$? Geometric graph is an image of a graph on a ...
5
votes
2answers
200 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 ...
1
vote
0answers
77 views

How to prove the NP-hardness of this scheduling problem

Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations ...
1
vote
2answers
142 views

Why is the decision problem of the “Travelling Salesman” $\in \mathcal{NP}$?

One of the most well-known problems that belongs into the class of $\mathcal{NP}$-complete problems is the Travelling Salesman Problem. However, I fail to see why it is "so obviously" in ...
0
votes
0answers
76 views

Solving a system of multivariate (possibly homogeneous) polynomials over $\mathbb{Q}_p$ efficiently

after an unsuccessful search for appropriate literature, I thought to post my question here: Suppose a system $F$ of $n$ polynomials in $n+1$ variables having coefficients in $\mathbb{Q}_p$: ...
0
votes
1answer
235 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 ...
2
votes
1answer
75 views

Homomorphical Equivalence is NP-complete

Two graphs $G,H$ are homomorphically equivalent if there are exists a homomorphism from $G$ to $H$ and a homomorphism from $H$ to $G$. The task is to prove that this decision problem ...
1
vote
1answer
57 views

Doubts related to set cover NP complete problem

I am trying to show that a problem is ${\sf NP}$-complete by reducing Set Cover to it. I have three sets, say $A = \{1, 3\}$, $B = \{1\}$ and $C = \{1, 2\}$. In my problem, I need to find the ...
1
vote
2answers
141 views

A Problem on Time Complexity of Algorithms

I want no know if the following problem is solved or not, or how can I solve it? Problem: For every integer $t$, Is there any problem that can be verified in $O(n^{s})$ but its solution can be found ...
4
votes
1answer
8k views

Is “P vs NP” problem solved?

Many people have tried to solve the very famous problem "P vs NP" and a lot of solutions are proposed. (e.g. A. D. Plotnikov, On the Relationship between Classes P and NP). But I couldn't find any ...
3
votes
1answer
114 views

Confusion related to the definition of NP problems

I have this confusion related to the definition of NP problems. According to wikipedia Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have ...
2
votes
2answers
252 views

transform traveling salesman problem into subgraph isomorphism problem

Lets say, I could solve subgraph isomorphism problem in constant time. How could I use this to solve traveling salesman problem? aka... how to transform traveling salesman problem into subgraph ...
0
votes
1answer
122 views

understing Cook theorem and input length

Following is my understanding of Cook theorem. Let P be a $\mathcal{NP}$ problem. And let M be a polynomial NDTM for P, $$ M(x) = \left\{ \begin{array}{ll} 1\text{ if x∈ P}\\ 0\text{ ...
0
votes
1answer
116 views

algorithm and Cook theorem

Let $A$ be a set of decision algorithms which are running in polynomial time and which takes natural numbers as inputs. $x\in A$ if and only if for $i\in N$ $x(i)=0$ or $x(i)=1$ ...
0
votes
1answer
179 views

About Cook–Levin theorem

I want to check whether I understand the Cook-Levin theorem fully (using the Travelling Salesman Problem as an example). Given a weighted graph $G$ and an number $L$, the a Travelling Salesman ...
1
vote
0answers
135 views

Permutation Strategy for Sudoku solver NP-complete?

We know that Sudoku itself is $\mathbf{\mathsf{NP}}$-complete, but while trying to implement the "Permutation Rule" strategy in my solver, I was unable to find an efficient algorithm to do so. The ...
2
votes
1answer
143 views

The Two Clique problem is in P or NP? P != NP for hypothesis.

I need to find a solution to the following question: The problem of the "Two Clique" is in P or NP-complete (assuming P != NP)? The "Two Clique" problem is the following: Given a graph G = (V, E), ...
2
votes
0answers
225 views

$NP$-completeness of scheduling problem

I have been attempting to show that this problem is NP -complete but haven't been successful. I wonder if anyone has a suggestion for a problem I could reduce to it. CALLS : Suppose we have nodes ...
1
vote
1answer
71 views

Proof of NP-completness for the foll0wing

I have encountered a problem similar to Set Cover (and Maximum Coverage): We have several sets in a universe with $N$ elements. What is the maximum number of sets so that the number of elements found ...
4
votes
1answer
144 views

NP-complete Problems

It seems from reading that problems are determined to be NP-complete if they can be shown to be equivalent to another NP-complete problem. However, I wonder how the "original" NP-complete problem was ...
-2
votes
1answer
225 views

Prove that every problem in P is reducible [duplicate]

Possible Duplicate: For two problems A and B, if A is in P, then A is reducible to B? Given two problems $A$ and $B$, if $A$ is in $\def\P{{\mathcal P}}\P$ then $A$ is reducible to $B$. ($A ...
9
votes
2answers
612 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 ...
3
votes
1answer
135 views

NP-hardness reduction

Although I know the notion of polynomial time reduction since many years, I am currently confused about the following problem. In a reduction from 3-SAT to 3-Coloring, one constructs (in polytime) a ...
1
vote
0answers
261 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 ...
2
votes
1answer
191 views

Using Polynomial-Time Reduction to Prove Hardness

From what I understand of polynomial-time reduction, there are two instances of it: many-one and Turing. Many-one simply breaks down problem A into many instances of problem B, and uses the (known) ...
0
votes
1answer
397 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
568 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) ...
4
votes
0answers
134 views

Connect 4 - SAT

My question is about how the Hasbro game Connect4 can be viewed as a SAT problem. My initial guess is that it would actually be QSAT, and that the 'problem' would be something along the lines of: "Is ...
3
votes
1answer
228 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 ...
4
votes
0answers
167 views

Proving NP-completeness (hardness) exercises

I am looking for a list of exercises that can be done to practice polynomial time reductions to prove NP-hardness of problems. I know there are hundreds (thousands?) of problems proven to be NP-hard. ...
5
votes
2answers
770 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
1answer
111 views

Polynomial-time reduction

How can I prove it? $A \le_p B \Leftrightarrow \overline{A} \le_p \overline{B}$. $A \in \mathcal P \Leftrightarrow \overline{A} \in \mathcal P$. $\overline{A} = \Sigma^* \setminus A$
1
vote
2answers
205 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 ...
4
votes
1answer
231 views

complexity theory: consequences of P vs NP

I have a basic question regarding the ramifications of P vs NP. If P=NP, then SAT would be in P. If I understand the definitions correctly, this would imply that there is a Turing machine which ...
4
votes
2answers
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!
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 ...
2
votes
1answer
93 views

Is it possible to remove exactly one solution from a CNF in polynomial time?

Given a conjunctive normal form (CNF) is it possible to remove one solution from its set of solutions (irrespective of whether the CNF has a solution or not in the first place)? By that I am asking if ...
1
vote
1answer
106 views

NP-hard problems which are easy on average

Are there any known NP-hard problems that are easy on average as per the definition of average-case complexity by Levin?