P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

0
votes
0answers
9 views

Circuity complexity: monotone circuit of Majority function

As showed in the paper "Monotone Circuits for the Majority Function", is possible to construct a monotone boolean circuit for the majority function on n variables with size O(n^3) and depth 5.3 ...
1
vote
1answer
32 views

Graph class with easy chromatic number, but NP-hard coloring

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard? Without any further restriction the answer ...
-2
votes
0answers
65 views

NP problems for which there exists “greedy” algorithms [on hold]

I suspect that a problem that can be solved to optimality by incremental improvements (ie a "greedy algorithm") can be said to be in NP if a polynomial time algorithm for computing the incremental ...
1
vote
0answers
66 views

NP Intermediate problems over Reals

While studying ${\bf NP}$ complete problems we have from Ladners' theorem - if ${\bf P}$ $\neq$ ${\bf NP}$-there are ${\bf NP}$ problems not in the class ${\bf P}$ nor ${\bf NP}$-complete. Ladners' ...
5
votes
1answer
69 views

A special case of the boolean multivariate quadratic polynomial problem

It's well known that in the general case, the boolean MQ problem: given $(f_1, \ldots, f_n) \in \mathbb{F}_2[x_1, \ldots, x_m]$ with $\deg(f_i) = 2$, can we find a solution $\vec{y}: f_i(\vec{y}) = ...
5
votes
0answers
119 views

The evaluation problem for AC$^0_d$ formulas is in FO

Let $d \in \mathbb{N}$ be arbitrary. Let $\mathsf{AC^0_d}$-Eval be the following promise problem: Input: A depth $d$ formula $\varphi(x)$ and a binary string $a$. Output: $\varphi(a)$ I am looking ...
16
votes
0answers
287 views
+50

Complexity of approximating the range of a matrix

Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define: $$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$ I believe that it is NP-hard to compute $S_M$ exactly, by applying ...
2
votes
0answers
227 views

Computational Complexity of Ramsey Numbers

What is the computational complexity of computing Ramsey numbers $(n,m) \mapsto R(n,m)$? Is it inside PH? Would it be easier to compute $R$ if PH=P?
3
votes
0answers
99 views

Complexity of minimizing monotone arithmetical formulas

Let's say that I have a multi-variate arithmetical expression $A(x_1, \ldots, x_n)$ that uses addition and multiplication operations and is also in a very simple form of sums of products, e.g., ...
-2
votes
0answers
55 views

Randomized and Deterministic Communication Complexity of a function [closed]

I have a problem I'm trying to answer for my homework. The question is: Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x ∈ GF(p)$ encoded ...
-3
votes
0answers
62 views

LTL with past time operators [closed]

you know a method for runtime verification of future time LTL which uses a monitor in automaton form and which has a constant computational complexity. Sketch a new method to do a runtime verification ...
10
votes
1answer
213 views

BQP algorithm for two graph bisection problems and its implications on NP $\subseteq$ BQP

I read the paper Ahmed Younes, "A Bounded-error Quantum Polynomial Time Algorithm for Two Graph Bisection Problems", 2015. doi:10.1007/s11128-015-1069-y which is published in Springer's journal ...
12
votes
2answers
320 views

How common is phase transition in NP-complete problems?

It is well known that many NP-complete problems exhibit phase transition. I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, ...
7
votes
2answers
203 views

How to find a non-zero point of a non-zero polynomial of low degree?

Given a circuit that computes a polynomial $P(x_1 \dots x_n)$ of low formal degree over some large field $\mathbb{F}$. Moreover, given a point $X \in \mathbb{F}^n$, such that $P(X) \neq 0$. Can one ...
1
vote
0answers
93 views

Linear Time Hierarchy and Circuit complexity

By Karp-Lipton Theorem we have: $$PH\subseteq P/poly\Rightarrow PH=\Sigma^p_2$$ So this theorem suggest it is unlikely that $PH\subseteq P/poly$. I want to know is there any similar conditional or ...
16
votes
1answer
377 views

Division by two of functions in #P

Let $F$ be an integer valued function such that $2F$ is in $\#P$. Does it follow that $F$ is in $\#P$? Are there reasons to believe this is unlikely to always hold? Any references I should know ...
4
votes
0answers
95 views

Lower Bound for Nonzero Terms of a Polynomial Fully Sensitive at 0

Every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be uniquely represented as a multilinear polynomial $p=\sum_{S\subseteq [n]}c_S \chi_s$ where $\chi_s=\prod_{i\in S}x_i$. A boolean function is ...
14
votes
1answer
219 views

Monotone arithmetic circuit complexity of elementary symmetric polynomials?

The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables. I am interested in the monotone arithmetic $(+,\times)$ circuit ...
13
votes
2answers
468 views

Regular versus TC0

According to the Complexity Zoo, $\mathsf{Reg} \subseteq \mathsf{NC^1}$ and we know that $\mathsf{Reg}$ cannot count so $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$. However it doesn't say if ...
1
vote
1answer
93 views

decision tree complexity and query complexity

I want good sources for starting with decision tree complexity and query complexity , what papers to start with ? what book chapters to read ? I already seen arora and barak book and I begin to read ...
0
votes
0answers
160 views

When can arguments for $\mathsf{NP}$ be replaced by $\mathsf{NEXP}$ by employing succinct circuits?

According to papers here https://users.cs.duke.edu/~reif/temp/RandomHardProblems/NovaFandina/succinctPermanent.pdf and here http://perso.ens-lyon.fr/natacha.portier/papers/PY86.pdf questions in ...
-1
votes
1answer
163 views

Parallels between communuication complexity and complexity theory

(1) Do we know the polynomial hierarchy $\mathsf{PH^{cc}}$ is infinite in communication complexity? (2) Is there a candidate problem in ...
0
votes
0answers
72 views

Find max weight induced graph in a multipartite graph with one vertex from each part

Consider the follow problem: Input: $G=(V,E)$, a weighted $k$-partite graph with $n$ vertices. Output: $U \subseteq V$, one vertex from each part, maximizing the total weight of the induced graph ...
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 ...
3
votes
1answer
230 views

Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?

May be this is trivial but I do not know the answer. As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds. As far as we know ...
10
votes
0answers
111 views

Hardness in P: methods to show optimality of $O(m^2n)$-like time?

In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in ...
15
votes
1answer
428 views

Is Dynamic Programming never weaker than Greedy?

In the circuit complexity, we have separations between powers of various circuit models. In the proof complexity, we have separations between powers of various proof systems. But in the ...
9
votes
1answer
148 views

Evaluating symmetric polynomials

Let $f:\mathbb{K}^n \to \mathbb{K}$ be a symmetric polynomial, i.e., a polynomial such that $f(x)=f(\sigma(x))$ for all $x \in \mathbb{K}^n$ and all permutations $\sigma \in S_n$. For convenience, we ...
5
votes
2answers
132 views

Popular average-case complexity assumptions

Except for planted clique and random 3SAT, what are the other commonly used average-case complexity assumptions?
2
votes
0answers
74 views

Is gaussian smoothing possible in less operations than O(N log N)

Gaussian filtering is popular in applications, for my question it can be written as (I've fixed the size of window): $$y_i = \sum_{j = 1}^{n} x_j e^{(i - j)^2}, \qquad i = 1, 2, ..., n $$ One can ...
2
votes
0answers
93 views

Are ill-posed inverse problems in NP?

I'm a physicist who works on inverse problems; I'll explain what these are by means of an example. Consider an object whose refractive index is known; then, the problem of computing scattered ...
3
votes
0answers
223 views

Possibility of weaker forms of $P = NP$

Assuming that $P \ne NP$ how surprising would it be if a weaker form of $P = NP$ holds? For example consider the following weaker forms of $P = NP$: $NP \subseteq DTime(2^{O(n^\varepsilon)})$ for ...
5
votes
2answers
268 views

Are there any propositional proof systems which are not Cook-Reckhow proof systems?

An abstract proof system is a polynomial time function $f$ whose range is equal to the set of tautologies. If $\tau$ is a tautology, then an $f$-proof of $\tau$ is any value $\pi$ such that ...
-1
votes
1answer
136 views

Are Graph and Group Isomorphism problems random self-reducible?

Are Graph and Group Isomorphism problems known to be random self-reducible? If so is there a good proof? Are there other non-trivial examples of random self-reducibility? Is there a good reference?
1
vote
0answers
21 views

Efficient compilation of interaction combinators with infinite cell types to usual interaction combinators?

It is known that interaction combinators can implement any interaction net system efficiently. Now, let us define a modification of interaction combinators, which, instead of two types of fan cells, ...
14
votes
2answers
206 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
152 views

Improving Cook's generic reduction for Clique to SAT?

I am interested in reducing $k$-Clique to SAT without making the instance much larger. Clique is in NP so it can be reduced to SAT using logarithmic space. The straightforward Garey/Johnson textbook ...
3
votes
2answers
216 views

Consequences of $NP\subseteq P/poly$ to $BQP$

A post here Consequences of $BQP \subseteq P/poly$? queried on Consequences of $BQP \subseteq P/poly$. It is not known if $NP\subseteq BQP$. In general, what are the consequences of $NP\subseteq ...
8
votes
2answers
203 views

Uncertainties in GCT program

In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. ...
2
votes
1answer
87 views

Algorithms for tree rotation

What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest ...
6
votes
3answers
341 views

Natural NP-complete problems with high density?

(This question is related to a previous one, see the discussion in "Almost easy" NP-complete problems, but it may also be of independent interest, so I post it as a separate question.) Let ...
4
votes
0answers
141 views

Complexity of a problem over acyclic context-free grammars

Let $G$ be an acyclic, context-free grammar over a fixed alphabet $\Sigma=\{a_1,\dots,a_k\}$ with the restriction (without loss of generality) that $|w|=2$ for each rule $A\to w$ in the grammar. ...
1
vote
1answer
142 views

Is this problem #P-hard and why?

Problem: In a directed graph $G=(V,E)$, each edge $e\in E$ is associated with a weight $w_e$ which is geometrically distributed with a parameter $p$, i.e. $P(w_e=i)=p(1-p)^{i-1}, i\geq 1$. $s,t$ ...
17
votes
1answer
476 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 ...
7
votes
1answer
196 views

Are there more polynomial time problems with complexity lower bounds?

I'm looking for more problems in $P$ with classical time complexity lower bounds. Some people might wonder how you could prove such a lower bound. See below. Exponential Lower Bounds: Claim: If ...
13
votes
1answer
159 views

2FA state complexity of k-Clique?

In simple form: Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states? Details Of interest here are $v$-vertex graphs encoded using a sequence ...
16
votes
2answers
385 views

Potentially equal complexity classes without known contradictory relativizations

What are some examples of pairs of complexity classes $A$ and $B$ such that we do not know whether $A=B$, and we do not know contradictory relativizations either (i.e., we do not know oracles $P$ ...
1
vote
0answers
42 views

Multicuts (or multiway cuts) for 3 Terminals of Minimum Capacity

For each fixed $k \geq 3$, the following well-known problem is NP-complete. k-Multicut (aka "Multiway Cut", "k-Way Cut", "Multicut") Input: $(N,l)$ where $N=(V,E,T,c)$ is an undirected $k$-terminal ...
6
votes
1answer
254 views

NP-hardness of coloring uniform hypergraphs

Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen ...
8
votes
1answer
215 views

Does the isomorphism conjecture imply exponential lower bounds on witnesses density?

The Isomorphism Conjecture of Berman and Hartmanis states that all $NP$-complete sets are polynomial time isomorphic to each other. This means that $NP$-complete problems are efficiently reducible to ...