Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [np-complete]

The tag has no usage guidance.

-1
votes
1answer
136 views

Will a non-linear lower bound on some NP complete problem prove non-linear lower bound on 3SAT?

A problem $\Pi$ is $\mathsf{NP}$ complete if there is a polynomial time reduction from an $\mathsf{NP}$ complete problem $\Pi^\circ$ to $\Pi$ with polynomial blow up on number of variables and ...
-5
votes
1answer
49 views

Can I prove this polynomial reduction?

Consider Barely-3-SAT: given a CNF $F=\wedge^m C_i$ determine whether there is an assignment such that exactly one clause $C_k$ is true all the others are false. I want to show this is $NP$-complete. ...
12
votes
0answers
424 views

Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?

Question I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete. Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$. Where $\...
11
votes
0answers
264 views

Error in paper “Some NP-complete geometric problems”?

The paper in question: M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems . This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
9
votes
0answers
168 views

Complexity question from mathematical music theory

Fix an positive integer $N$. A row means any linear ordering $R=(n_i)_{0\leq i <N}$ of the additive group ${\Bbb Z}/N{\Bbb Z}$. Call $R$ a (generalized) all-interval row if the elements of the ...
8
votes
0answers
127 views

Practical interactive proof schemes for NP-hard problems

Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on ...
8
votes
0answers
184 views

What would be the consequences if all _infinite_ NP-complete languages are p-isomorphic?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic ($p$-isomorphic) to each other. It has been an early attempt (published ...
7
votes
0answers
52 views

Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times

When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem: Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
6
votes
0answers
248 views

On the shortest vector problem (is it $NP$-complete?)

Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum. Has this been derandomized?
6
votes
0answers
185 views

When will an NP-complete language remain hard if half of a witness is revealed with the instance?

Let $L$ be an NP-complete language. Let $W(x)$ denote the set of (polynomially length bounded) witnesses that certify $x\in L$. That is, $x\in L$ if and only if there exists a $w$, such that $w\in W(...
6
votes
0answers
178 views

Generalization of SAT, where we replace OR with another symmetric function

Let $\sigma(y_1,\dots,y_k)$ denote some boolean symmetric function on $k$ boolean inputs, $\sigma:\{0,1\}^k\to\{0,1\}$. In $k$-SAT, an instance is a conjunction of clauses, where each clause is the ...
5
votes
0answers
116 views

Question about a unary language construction

For any language $L$, let us define another language $Tally(L)$, as follows: $$Tally(L)=\{1^n\;|\;\exists x \;\mbox{with}\; x\in L \;\mbox{and}\; |x|=n\}$$ That is, $Tally(L)$ encodes whether there is ...
4
votes
0answers
160 views

Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular ...
4
votes
0answers
130 views

Symmetry of optimal solutions to discrete optimization problems

Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than ...
3
votes
0answers
206 views

new subset sum approach results

I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $O{n/2 \choose n/4}$, demonstrating as well the hardest target value is ...
2
votes
0answers
118 views

Space time lower bound with $\mathsf{PSPACE}$ oracle

Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem? ...
2
votes
0answers
152 views

Looking for reference on NP-Completeness of proofs of length n

Given a deductive system $\Lambda$, and some well-formed-formula S, one can ask the question "Is there a proof S in $\Lambda$ of length n?" If n is presented in base-1 and if all the axioms of $\...
2
votes
0answers
147 views

Bijection between NP-complete problems

If $A$ and $B$ are NP-complete problems, is there a bijective function $f$ (computable in polynomial time) such that $w\in A$ iff $f(w)\in B$?
2
votes
0answers
200 views

Which complexity information of Ising model is more important?

In 1982, Barahona proved that finding the ground state of an Ising model is NP-hard. Later, in 2000, Istrail proved that it is NP-complete. When I look up the citations of these two papers using ...
1
vote
0answers
20 views

Assumption of unique shortest paths in subcubic reduction

In the paper "Subcubic equivalences between graph centrality problems, APSP and diameter", it is shown that the all pairs shortest path problem (APSP) and the problem of computing the betweenness ...
1
vote
0answers
95 views

Generalized path cover problem in DAG

Let $G=(V,E)$ be a directed acyclic graph. Two vertices is transitive if there is a directed path between them. A Path Cover for a Set of Transitive Pairs (PCSTP) is a set of directed paths such that ...
1
vote
0answers
72 views

Prove that finding set of $k$ vertices $S$, such that $G{\setminus}S$ is claw-free is NP-Complete

The claw in a graph $G(V,E)$ consists of a vertex $v\in V$, and it's three neighbours - $\{x_1,x_2,x_3\}\in V\setminus \{v\}$, if $\{x_1,x_2,x_3\}$ form an independent set in $G$. The problem asks us ...
1
vote
0answers
90 views

About representability of optimization versions of NP-complete questions as polynomial optimization over the hypercube

Naively, in my very limited awareness, it feels that the Max-CUT is a very "special" NP-Hard problem because for a graph with edge-set $E$, it can be written as the question of trying to maximize a $n$...
1
vote
0answers
74 views

Distributing bags of apples equally

Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags ...
1
vote
0answers
250 views

Finding an equivalent NP-complete instance for this game-theory problem

I apologize if this question is not a good fit for CSTheory. I'm a PhD student who has just started out and I'm working on a game-theory problem in one of my classes. Although my professor hasn't ...
1
vote
0answers
837 views

Is there a reduction from a 0-1 knapsack problem to the unbounded problem?

As we know, an unbounded knapsack problem could be described as: $\max \sum_{i=1}^nc_1x_i$ s.t. $\sum_{i=1}^na_ix_i\le b$ $x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$ And for an 0-1 knapsack problem, we ...
1
vote
0answers
121 views

Properties of “second-order” NP (complete) languages

Reading the question Natural NP-Complete Problems with Large Witnesses, I was interested in this language: $L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ ...
1
vote
0answers
596 views

Are there upper bounds on the worst case complexity of NP-complete problems?

I have proven some problem to be (weakly) NP-complete and try to find out some algorithm to solve it exactly. Except for some pseudo-polynomial stuff, I would be happy with an algorithm running in $O(...
0
votes
0answers
82 views

distNP-complete problem

Here on page 367 there is an example of $\text{dist}\mathbb{NP}$-complete problem: let $U$ contain all tuples $\langle M,x,1^t\rangle$ where there exists a string $y\in \{0,1\}^l$such that the ...
0
votes
0answers
27 views

Satisfying two constraint with an oracle for satisfying one

Given an oracle to solve the knapsack feasibility problem: $$a^Tx=b, x \in \mathbb{N}^n$$ How can one solve in polynominal time the problem of satisfying two constraints at the same time? I already ...
0
votes
0answers
61 views

Complexity of variant polynomial factorization

Few years back a question on whether a variant of integer factorization was $\mathsf{NP}$ complete was asked, which according to state of mathematics today does not have a conclusive answer. Is ...
-4
votes
0answers
74 views

Prove that if A is NP-complete and B is coNP-complete, than AxB is NP-, coNP-complete

AxB means cartesian product of A and B. May someone help me with this? I even have no idea how to prove that AxB belongs to NP or coNP