The tag has no usage guidance.

learn more… | top users | synonyms

6
votes
1answer
152 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 ...
1
vote
0answers
69 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 ...
0
votes
0answers
24 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 ...
6
votes
0answers
142 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 ...
5
votes
1answer
106 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()$ ...
6
votes
1answer
126 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 ...
6
votes
1answer
265 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
66 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 ...
6
votes
1answer
235 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
200 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?
1
vote
2answers
287 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
213 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 ...
7
votes
1answer
307 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 ...
17
votes
1answer
494 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 ...
11
votes
4answers
624 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 talk at University of Illinois, Chicago, note from the talks by Jeremy Kun GLL post 1, GLL post ...
1
vote
0answers
72 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 ...
12
votes
1answer
204 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$. ...
21
votes
3answers
470 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
84 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
43 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 ...
-3
votes
1answer
212 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
360 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
78 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
86 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
105 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
45 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 ...
-3
votes
1answer
62 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
183 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
169 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
133 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
275 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 ...
2
votes
0answers
141 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 ...
0
votes
0answers
77 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
227 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
198 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
216 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
91 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
86 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 ...
5
votes
1answer
331 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
74 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 ...
2
votes
1answer
233 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
125 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 ...
9
votes
0answers
139 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
384 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 ...
17
votes
1answer
355 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 ...
8
votes
1answer
265 views

Can a natural graph problem be universally hard?

Is there a natural $\mathsf{NP}$-complete graph problem, which remains $\mathsf{NP}$-complete even when it is restricted to any polynomial-time recognizable graph class? To avoid degenerated cases, ...
2
votes
1answer
420 views

Multiple subset sum where subsets have complementary cardinality

$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem: Input: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$. Output: $k$ $\mbox{ ...
3
votes
0answers
104 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 ...
4
votes
1answer
192 views

Are there any implementations for zero-knowledge proofs of NP-complete problems?

It's been known for a long time that any claim in NP has a zero-knowledge proof for it. Has anybody actually implemented a zero-knowledge proof system for a NP-complete language? Using a search ...