Questions tagged [np-complete]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
8
votes
0answers
280 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 ...
-5
votes
1answer
135 views

Dance Partner Problem NP-completeness [closed]

I really can't think of a concise way to phrase this problem, which makes it hard to search for, so forgive me if this is a duplicate question. I've come across a problem and I would like to know if ...
-3
votes
1answer
137 views

Could you explain to me the reduction? [closed]

I am looking at the following solved exercise: I haven't really understood at the reduction the part that we construct for each number $a_i$ a package of measurement $(\frac{4}{A}a_i, 5,3)$. Why do ...
5
votes
1answer
165 views

Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

Consider the following problem P: Input is a finite graph G. If the number of vertices in G is 2^2^i for some integer i, then output a minimum vertex cover of G; otherwise output empty set. Can I say ...
8
votes
1answer
253 views

NP-hardness on Cayley graphs

What is known about complexity of NP-hard problems on Cayley graphs? Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
7
votes
1answer
292 views

Problem of graph bi-partition (related to graph isomorphism)

I am considering the following problem: Input: 3 graphs $G=(V,E)$, $H_1$, $H_2$ Question: Is there some $V_1\subseteq V$ such that $G[V_1]$ (the subgraph induced by $V_1$) is isomorphic to $H_1$, ...
2
votes
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$...
5
votes
0answers
192 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(...
5
votes
1answer
164 views

Analogues of the Berman Hartmanis conjecture and the Creativity Hypothesis

The Berman Hartmanis conjecture which formally states that there is an isomorphism for two $NP$ complete languages $L_{1}$, and $L_{2}$, the isomorphism is a bijective function $f()$ such that $f()$ ...
5
votes
1answer
163 views

Does p-isomorphism preserve phase transition?

Consider two NP-complete languages that are polynomial-time isomorphic. If we know that one of them exhibits phase transition (with respect to some order parameter), does this imply that the other ...
5
votes
1answer
344 views

On Zero sum perfect matching

Fix $c\geq1$. Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order. Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of ...
2
votes
0answers
110 views

An NP-complete variant of factoring and relation to factoring [closed]

After reading this post An NP-complete variant of factoring. I come up with a question. To summerize the post, we have the factoring problem (F) which ask for a number $p$ that is prime and divides ...
7
votes
1answer
272 views

Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

A set is $\mathsf{P}$-immune iff it has no non-trivial $\mathsf{P}$ subset. Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to an $\mathsf{P}$-immune $\mathsf{coNP}$-complete ...
4
votes
2answers
235 views

Partition graph into 2 or more claw-free subgraphs

Is it NP-hard to partition the vertex set of graph G into k subsets so that they induce k claw-free subgraphs of G?
0
votes
2answers
407 views

NP completeness of linear $0-1$ assignment problem

Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each. Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables ...
14
votes
2answers
353 views

Poly time superset of NP complete language with infinitely many strings excluded from it

For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite? A trivial version which does not stipulate the superset to have infinite ...
10
votes
1answer
499 views

Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

Berman–Hartmanis conjecture: all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms[1]. I am interested in a more fine-grained ...
20
votes
1answer
687 views

“Almost easy” NP-complete problems

Let us say that a language $L$ is P-density-close if there is a polynomial time algorithm that correctly decides $L$ on almost all inputs. In other words, there is an $A\in$ P, such that $L\Delta A$...
17
votes
4answers
2k views

Is there a natural problem in quasi-polynomial time, but not in polynomial time?

László Babai recently proved that the Graph Isomorphism problem is in quasipolynomial time. See also his talk at University of Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post 2, GLL ...
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 ...
13
votes
1answer
245 views

Slowest many-one reduction?

When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. ...
23
votes
3answers
911 views

How much would a SAT oracle help speeding up polynomial time algorithms?

Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ ...
4
votes
1answer
106 views

NP-Complete Convergent Reductions?

A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the ...
3
votes
0answers
56 views

Is this permutation-sum problem NP-complete? [duplicate]

A new, tighter tardiness bound has been found for global Earliest-Deadline-First scheduling of jobs on symmetric multiprocessors. But this bound seems to be particularly hard to compute. In particular,...
-3
votes
1answer
304 views

Consequences of polynomial time algorithm to variant of integer factorization

Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring. So supposing ...
12
votes
1answer
385 views

Which complexity class does this number theory problem belong to?

'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete. Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
5
votes
0answers
161 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 ...
2
votes
0answers
123 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? ...
-1
votes
1answer
138 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 ...
0
votes
0answers
65 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
1answer
149 views

How to reduce LCS from Vertex-Cover [closed]

I am trying to understand the demostration of intractability of the LCS problem, as stated as a reduction from Vertex-Cover problem, and so far, i'm stuck with the demostration of the problem in this ...
7
votes
1answer
211 views

What do we know about checking real-stability of multivariate complex polynomials?

Given a polynomial $p : \mathbb{C}^n \rightarrow \mathbb{C}$ it is to be called "real-stable" if (1) all its coefficients are real and (2) if it has no roots such that all the coordinates of the root ...
1
vote
0answers
261 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
909 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 ...
-7
votes
1answer
3k views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
4
votes
1answer
221 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
185 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
386 views

Subset sum solver. Worth continue working on this method? [closed]

I have been working in a subset sum problem solver for some time. The implementation is an exact/exhaustive search solver. The variable determining the asymptomatic growth rate is just $N$ (the ...
2
votes
2answers
243 views

Balls & Bins: A punishment and reward game

Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$. The rules of the game are as follows: (1) Once a bin has a ...
4
votes
1answer
230 views

Is the problem NP-C or polynomially solvable?

I am considering a problem of the following: Given a set $X$ of integers and another integer B, are there two subsets of $X$, say $X_1$ and $X_2$, such that $X_1-X_2=B$ ? (Here, $X_i$ also denotes the ...
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{ ...
2
votes
0answers
259 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 ...
6
votes
1answer
576 views

Does the Cook-Levin theorem relativize?

My only motivation for asking this question is long-standing curiosity, but I am interested in seeing a proof (or disproof) that the Cook-Levin theorem relativizes. If you have a proof that the ...
0
votes
1answer
121 views

Flow networks: Push flow on either edges but not both!

I have a flow network with random capacities on edges, is there some way to add a constraint of the type (push flow on either one of these two edges but not on both)? I'm not sure if this is correct ...
6
votes
1answer
2k views

Magic constant to solve NP-complete problem in polynomial time

Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial ...
3
votes
1answer
523 views

Easier and Harder instances of NP-complete problems?

Following previous questions here and here around $NP$-complete problems (and P vs NP). Are there "easier" or "harder" (sets of) instances of an $NP$-complete problem? If yes (which i assume), how a ...
0
votes
1answer
159 views

Any result connecting an NP-complete problem with slight super-polynomial time?

Helo everybody, is there any result or research that connects some $NP$-complete problem with only slightly super-polynomial (strongly sub-exponential) time? This would not necessarily involve ...
9
votes
0answers
171 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 ...
5
votes
2answers
486 views

Proof for ACYCLIC PARTITION being NP-complete

I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers. I'm interested in reading any proof of ACYCLIC PARTITION (Garey and ...
18
votes
1answer
440 views

Natural candidate against the Isomorphism Conjecture?

The famous Isomorphism Conjecture of Berman and Hartmanis says that all $NP$-complete languages are polynomial time isomorphic (p-isomorphic) to each other. The key significance of the conjecture is ...