P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

2
votes
1answer
62 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
90 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
132 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
56 views

Problems needs solutions in Distributed computing?

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
116 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
183 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 ...
-1
votes
0answers
26 views

Computational complexity for linear discriminant analysis [closed]

The linear discriminant analysis algorithm is as follows: I want to conduct a computational complexity for it. For each step, the complexity is as follows: For each $c$, there are $N_cd$ ...
0
votes
0answers
69 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
129 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 ...
-1
votes
0answers
69 views

Can a search problem be NP-hard? [migrated]

The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand. If we have an NP problem where know that ...
7
votes
0answers
46 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
236 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
451 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 ...
6
votes
2answers
292 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
443 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
77 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
58 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
78 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
193 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 - ...
11
votes
2answers
149 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
179 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 ...
8
votes
0answers
64 views

Is there a counting complexity class for succint problems?

Encoding NP-complete problems succintly often makes them NEXP-complete. I am wondering if counting the number of solutions to such a problem with a succint encoding would be any harder than solving ...
8
votes
2answers
264 views

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

In the movie Inception Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource ...
1
vote
0answers
75 views

k-wise Independence vs. Min-entropy

A distribution $D$ on $\{0,1\}^n$ is $k$-wise independent if any $k$ of the underlying $n$ random variables are independent and each is uniformly distributed. To me this looks similar in spirit to $D$ ...
11
votes
2answers
283 views

Scope of natural proofs barrier

The natural proofs barrier of Razborov and Rudich states that under credible cryptographic assumptions one cannot hope to separate NP from P/poly by finding combinatorial properties of functions that ...
5
votes
0answers
132 views

Is MAX-SAT SETH (like) hard?

If we make a random assignment to the variables in $k$-sat ($m$ clauses), we are going to satisfy $(1-2^{-k})m$ clauses in expectation. In general satisfying fewer clauses is considered easy. There ...
10
votes
1answer
115 views

Can differential equations be classed into their own complexity classes?

Problems have been, as a whole, classified, thanks to Computational Complexity. But, in differential equations, is it possible to classify differential equations depending on their computational ...
8
votes
2answers
317 views

Partition of a set of integers into subsets with prescribed sums

I saw this problem: A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be n-realizable if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets ...
28
votes
7answers
3k views

Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
-2
votes
1answer
104 views

Why can't Horn-SAT be solved in Log-space? [closed]

A simple algorithm for Horn-SAT (in CNF) is the following: Given: A Horn formula $\phi$ in CNF. Find a unit clause (a clause with one literal) $C_i$. $~$Set the variable $x_j$ appearing in $C_i$ to ...
0
votes
1answer
109 views

Many-one reduction from inequality problem to equality problem

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is: ...
29
votes
2answers
584 views

Is there an oracle such that SAT is not infinitely often in sub-exponential time?

Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all ...
5
votes
1answer
161 views

possible bridge between group growth theory and complexity theory?

RJ Lipton conjectures a link between group growth theory and complexity theory. Group growth theory has undergone rapid advance in the last decade and has many surface similarities/ parallels with ...
6
votes
1answer
125 views

Nondeterministic communication complexity of set disjointness?

In the two-party setting, bounds of $\Theta(n)$ bits are known for deterministic and bounded-error randomized protocols for $\text{DISJ}_n$. (Here $\text{DISJ}_n$ is the $n$-element set disjointness ...
-2
votes
1answer
109 views

Deciding CL-IS on graph efficiently

Given an arbitrary graph $G$, could there be a polynomial time algorithm to tell if it has a larger size clique $(\omega(G))$ or larger independence number$(\alpha(G))$?
4
votes
1answer
148 views

Introductions to steganography from an information-theoretic standpoint

Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
3
votes
1answer
121 views

Comparison between the maximum clique and maximum biclique problem

It seems to be commonly believed that the maximum biclique problem (on a bipartite graph) is more difficult than the original maximum clique problem. Is there a formal proof for this claim? (For ...
4
votes
0answers
91 views

An oracle relative to which EXP(NP) = BPP

Whether or not $\mathbf{BPP} = \mathbf{EXP}^{\mathbf{NP}}$ is an open problem, although we believe the former is strictly contained in the other. I guess, from the absence of the proof of the ...
24
votes
4answers
3k views

If P = NP were true, would quantum computers be useful?

Suppose that P = NP is true. Would there then be any practical application to building a quantum computer such as solving certain problems faster, or would any such improvement be irrelevant based on ...
0
votes
1answer
225 views

NP-complete problems with optimal approximation in poly-time

I'm looking for examples of hard optimization problems, for which we have an optimal approximation (not that this is not the same as $PTAS$, as we require a completely tight approximation, and not ...
20
votes
5answers
575 views

Curious about computer-assisted NP-completeness proofs

In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that ...
0
votes
1answer
103 views

What is the Algorithm to find all the possible chordal graphs which can be formed by a given 'n' number of vertices

A chordal Graph is a connected graph which contains no chord-less cycle of size greater than three. They are also called as Triangulated graphs. All Paths are Chordal Graphs (No cycles). All Trees ...
9
votes
1answer
465 views

Is the complexity of this path problem known?

Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 0$. Question: Does there exist an $s-t$ path in $G$, such that the path intersects at most $k$ ...
4
votes
1answer
336 views

The complexity of a multi-objective shortest path problem

I have the following shortest path problem. Consider a directed graph with $n$ levels. Each level has $m$ nodes. Each node at level $i$ is connected to all nodes at level $i+1$. Let us also make a ...
14
votes
1answer
358 views

Integer linear programming in logarithmic number of variables

I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in ...
10
votes
2answers
241 views

Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes. ...
5
votes
1answer
70 views

Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
3
votes
1answer
119 views

The relationship between completeness and strength of reductions

Ladner theorem can be stated as: $P \ne NP$ if and only if there exists an incomplete set in $NP-P$. Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time ...