P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

10
votes
0answers
109 views

Can we not output the Kolmogorov complexity?

Let us fix an encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ outputs whatever $T$ outputs on input $x$ (possibly both running forever). Define the Kolmogorov ...
0
votes
0answers
23 views

Test DataSet Generator for Monotone NAE 3SAT Algorithm

Can someone point to a configurable (var/clause count etc.) difficult problem set generator for testing an 3SAT algorithm that are challenging for current algorithms.. specifically NAE 3SAT data set ...
7
votes
0answers
121 views

What would signify hierarchy collapse to first level?

We know that $$\mathsf{NP\subseteq P/Poly \iff coNP\subseteq P/Poly\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P}$$ $$\mathsf{NP\subseteq P/Log\iff coNP\subseteq P/Log\implies PH=\Sigma_0^P=\Pi_0^P}$$ ...
4
votes
1answer
157 views

Complexity of algebraic problems

I am looking for a list about complexity of various numerical/algebraic problems. E.g. $GCD\in NC^1$ is open. factoring is in $P$ is open. computing sheaf cohomology is $\#P$-hard. [Arora and ...
0
votes
0answers
62 views

Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $

[This is NOT a research level question] I was reading the following paper by Jim Kadin: $P^{NP[O(\text{log } n)]}$ and sparse turing complete sets for NP. ...
-2
votes
1answer
40 views

Solving Modular System Ax = y with constraint that x is a Bit Vector

Note that I adapted the problem from (0,1)-vector XOR problem. I'm wondering if there is a polytime solution. Let $v_1,...,v_n,y \in \mathbb{Z}_m^a$. Does this system have a solution with the ...
6
votes
0answers
168 views

Is there a program for theory of incompleteness in $NP$?

Motivated by Suresh's post, Techniques for showing that problem is in hardness limbo, it seems that there might be an underlying theory that explains why some of these problems can not be complete for ...
2
votes
1answer
62 views

Knapsack combining sum and product

I cannot find references concerning the complexity of the variant of the knapsack problem (decision version) where one of the two conditions must be a product instead of a sum (0 not allowed). A ...
1
vote
0answers
60 views

Complexity: simulated annealing vs. quantum annealing

How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms? In Convergence theorems for quantum annealing by Morita and Nishimori, it has been ...
1
vote
0answers
43 views

complexity of factoring multivariate polynomials over Fn

recently multivariate polynomial factoring has been related to Polynomial Identity Testing / PIT (by Kopparty, Saraf, Shpilka). where is the complexity of factoring multivariate polynomials over ...
0
votes
1answer
71 views

Finding the maximum flow network and some contradiction claims? [closed]

I studying about NP, P and NP-Complete on Computational Course, and get stuck in one definition: we have an example to determine following is in NP or not: ...
-3
votes
0answers
62 views

Computational Complexity of 'Generic'/'Relaxed' Horn 3SAT [closed]

Horn 3SAT are described as the 3SAT with at most one positive literal. And its in P. What about the complexity of relaxed case of 2-Horn 3SAT i.e. Each clause is in CNF, has exactly 3 literals, with ...
0
votes
2answers
149 views

Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974). I am wondering if it is also known whether ...
22
votes
0answers
382 views
+50

Is Hankelability NP-hard?

I asked this question on SO on April 7 and added a bounty which has now expired but no poly time solution has been found yet. I am trying to write code to detect if a matrix is a permutation of a ...
2
votes
0answers
67 views

Is minimizing sum of distances hard?

The Problem Given a set of $n$ points $S = \{v_1, v_2, \cdots, v_n\} \subset \Re^d$, find a unit vector $s \in \Re^d$ such that $s$ minimizes $$ \sum_{i=1}^{n}\sqrt{\|v_i\|^2 - \langle v_i, s ...
9
votes
0answers
133 views

Second Smallest $s$-$t$-Cut in a Network

Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem: Input: A network $N$ and a number $k$, all in binary. Output: A $k$th smallest ...
8
votes
0answers
230 views

Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
6
votes
0answers
97 views

Problems in BQP but conjectured to be outside P

Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain ...
3
votes
1answer
185 views

#P- vs PP-Completeness

Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are ...
5
votes
1answer
168 views

Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
4
votes
0answers
89 views

Rigid families of $\{0,1\}$ matrices

We know that there are many families of matrices over $\Bbb F_q$, $\Bbb R$ etc are rigid. See http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf Do we know there are many families of rigid REAL ...
0
votes
1answer
115 views

What is the intuition behind “hardness of approximation”? [closed]

I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem. To my surprise, some closely related NP-hard problems are quite ...
0
votes
1answer
300 views

On straight line factorial calculation [closed]

If there is no straight line program that uses at most $\log^c n$ constants for a fixed $c$ to compute $n!$ in at most $\log^d n$ steps for a fixed $d$, then $\mathsf{P}_\Bbb C\neq\mathsf{NP}_\Bbb C$. ...
16
votes
0answers
207 views

What is the evidence for average case separation between EXP and NEXP?

There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way ...
2
votes
1answer
154 views

NP-hardness of minimum distance over a code

There happens to be this NP-complete question, Minimum-Distance-Over-$\mathbb{F}_{2^m}$ Given $w \in \mathbb{Z}^+$ and a $r \times n$ matrix $H$ over $\mathbb{F}_{2^m}$, is there a $x \in ...
24
votes
5answers
3k views

Is it a rule that discrete problems are NP-hard and continuous problems are not?

In my computer science education, I increasingly notice that most discrete problems are NP-complete (at least), whereas optimizing continuous problems is almost always easily achievable, usually ...
17
votes
2answers
546 views

Complexity of the recovery of an adjacency matrix from its square

I am interested in the following problem: Given an $n\times n$ matrix, is there an undirected graph on $n$ vertices whose adjacency matrix squared is that matrix? Is the computational complexity of ...
14
votes
0answers
237 views

Can short-distance connectivity be harder than connectivity?

Has anybody seen the following (or similar) question being considered: Can it be easier to determine the presence/absence of $s$-$t$ paths than to determine the presence/absence of short $s$-$t$ ...
2
votes
0answers
47 views

Hardness of approximately counting independent sets with a PRAS, rather than FPRAS

It is known that approximately counting the independent sets of a graph is hard, even if randomness can be used, and even if we restrict ourselves to bounded degree graphs with degree bound at least ...
4
votes
1answer
106 views

Communication complexity of Independent Set game?

Consider the following communication game. Independent Set game Let $[n] = \{0,1,\dots,n-1\}$ and let $r$ be a positive integer smaller than $n/(1+\log n)$. Alice receives a set $X$ of edges, each ...
0
votes
1answer
130 views

What are multiple rounds of SOS/Lasserre hierarchy?

Is that the same as saying the one will try to generate a higher-degree "pseudo expectation functional" by solving a SOS-program ? Or is there a difference between the two things? Or to take a ...
1
vote
1answer
169 views

The Goemans-Williamson algorithm in the $SOS$ framework

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, ...
-1
votes
0answers
60 views

Problems needs solutions in Distributed computing? [duplicate]

This is same as question. The answer for the question is 3 years old. Since the old topics will be quickly outdated or solved and new research problems arises, it would be great to know the latest ...
1
vote
1answer
127 views

What is a “level-r pseudo expectation functional”?

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
11
votes
0answers
196 views

Impact of proof of NP=co-NP on RP vs co-RP Question?

It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world: If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions? If NP=PSPACE, does RP=co-RP=ZPP ...
0
votes
0answers
70 views

Which n-qubit Hamiltonians are measurable in poly-time?

Which n-qubit Hamiltonians (or, equivalently Hermitian operators) can feasibly be measured in polynomial time? (as opposed to simulated in poly-time) What the relationship to the complexity of the ...
1
vote
0answers
137 views

What's the Impact if proven NP/co-NP=PSPACE on settling P=NP? The future directions it opens to settle/attack P=NP? Remaining classes left outside?

The primary Impact i know would be that: Polynomial Hierarchy collapses to Level 1. NP=co-NP NP=BPP NP=PSPACE BQP=NP and so on.. What are the attack directions it will open for settling P=NP (in ...
7
votes
0answers
52 views

Number of non-isomorphic induced subgraphs of a graph

Given a simple undirected grap, how many induced subgraphs does it have that are not isomorphic to each other? (or in a descision version, does it have fewer than k non-isomorphic induced subgraphs). ...
5
votes
1answer
241 views

Is it $NP$-complete to decompose bridgeless cubic bipartite graph into edge-disjoint paths of length 3?

Motivated by this post on cubic graphs decompositions, I am interested in decomposing a connected bridgeless graph into edge-disjoint paths of length 3 (P4). My intuition is that it should be ...
20
votes
0answers
467 views

What are consequences of the collapse of CH?

I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important ...
7
votes
2answers
305 views

Generalized Geography on graphs of bounded treewidth

Generalized Geography (GG) is played on a directed graph where a token is moved along arcs alternatively by two players. The vertices from which the token leaves are deleted. When a player cannot play ...
20
votes
2answers
455 views

How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$?

How fast would a nondeterministic algorithm for an EXPTIME-complete problem have to be to imply $P \neq NP$? A polynomial time nondeterministic algorithm would immediately imply this because $P \neq ...
1
vote
0answers
102 views

Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
11
votes
2answers
1k views

To which complexity class does this language belong?

I was thinking about which class this language belongs: $L =\{ \langle G,k \rangle \mid G $ is a graph, $k$ is a natural number and $k$ is the chromatic number of $G\}$ I thought of $L$ as (1) " ...
7
votes
1answer
1k views

Several papers appear to imply P=NP via chordal graphs, what is wrong?

Several papers appear to imply P=NP via chordal graphs, which suggests something is wrong. As usual $\gamma(G)$ is the domination number and $i(G)$ and $\gamma^i(G)$ are the independence domination ...
1
vote
0answers
60 views

What is the minimal known space for polytime algorithms

Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured ...
6
votes
1answer
83 views

Maximum number of geometrically disjoint paths - is the complexity known?

Let $G$ be an undirected graph, given with a planar drawing. We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct ...
8
votes
1answer
230 views

About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - ...
12
votes
2answers
156 views

Above #P and counting search problems

I was reading the wikipedia article about the eight queens problem. It is stated that, there is no known formula for the exact number of solutions. After some searching, I found a paper named "On the ...
3
votes
2answers
182 views

Why is $\{0,1\}^n$ referred to as the Boolean hypercube?

I used to view it just as a set of bit strings of length $n$. What does it mean for it to be the Boolean hypercube? Does viewing it from the hypercube perspective give a useful insight in a certain ...