Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
781
questions with no upvoted or accepted answers
5
votes
0
answers
309
views
Total time complexity of convex hull problem
The convex hull problem is to compute the facets of the convex hull of finitely many given points in $\mathbb{R}^d.$ By cone polarity it is equivalent to computing the vertices and rays of a ...
5
votes
0
answers
213
views
On permanent of $\{\pm1,0\}$ matrices
Consider the problem of computing the permanent $Per(M)$ of a matrix $M\in\{0,-1,1\}^{n\times n}$ such that the result is bounded in absolute value, $|Per(M)|<B$ where $B$ is part of input.
Is ...
5
votes
0
answers
203
views
Easy interactive proofs for easy problems?
Motivation
Consider some $L \subseteq \{0,1\}^*$. Suppose Alice gives Bob a machine or oracle $M$ that purportedly decides $L$. If Bob has only polynomial time in their disposal, then they cannot ...
5
votes
0
answers
156
views
Complexity of finding primes in arithmetic progression
By the Green-Tao theorem the prime numbers contain arbitrarily long arithmetic progressions. What is the computational complexity of the search problem in which the input is a natural number k encoded ...
5
votes
0
answers
412
views
About the ``recent" paper by Razborov in the Annals of Mathematics
Recently this paper on complexity theory was published at the Annals of Mathematics by Razborov, http://annals.math.princeton.edu/2015/181-2/p01. Curiously this seems to have been submitted to the ...
5
votes
0
answers
242
views
NP-completeness of a specific topological sorting problem
Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a ...
5
votes
0
answers
88
views
Computational depth and p-time hard instances
After reading the nice results of the paper: "Worst-Case Running Times for Average-Case Algorithms" by Antunes and Fortnow, I was wondering about the existence of further results linking basic ...
5
votes
0
answers
237
views
Testing Isomorphism of projective planes
Miller showed that isomorphism testing of projective planes can be done in $v^{O(\log \log v)}$. I would like to know whether Babai's techniques that led to the quasipolynomial time algorithm for GI ...
5
votes
0
answers
77
views
Finding of dimension of algebraic varieties
I have found that the problem of finding of dimension of algebraic varieties over $\mathbb{C}$ is $NP$-complete (https://pdfs.semanticscholar.org/a947/463a29ee512b89823176f6e8c9f9b2bb1a5e.pdf).
Are ...
5
votes
0
answers
208
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
0
answers
247
views
Maximizing the number of selected edges with opposing requirements
Consider the following problem:
Input: a complete bipartite graph $G$ with its edges colored either white or black, a number $k$.
Output: a subset of vertices $W$ of size $k$ which maximizes the ...
5
votes
0
answers
164
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 for ...
5
votes
0
answers
254
views
What is the status of Determinantal Complexity of Permanent
Recently Landsberg and Ressayre announced an exponential lower bound for permanent's determinantal complexity assuming certain symmetry conditions.
What is the status of the problem of Permanent's ...
5
votes
0
answers
199
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 ...
5
votes
0
answers
331
views
EXPTIME-complete propositional satisfiability problem
SAT is NP-complete, QBF is PSPACE-complete, DQBF is NEXPTIME-complete. Is there any extension of QBF or restriction of DQBF that is EXPTIME-complete?
Added later: a definition of DQBF can be found ...
5
votes
0
answers
128
views
Learning Finite Automata Behavior by Experimentation
This conjecture is from an expert in Game Theory area, I post it here to draw more attentions of TCS experts. Discussions and comments are welcome.
http://gtcenter.org/WCS_Call_for_papers.pdf
An ...
5
votes
0
answers
256
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 ...
5
votes
0
answers
489
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 ...
5
votes
0
answers
133
views
Implications of a deterministic polytime prime-finding algorithm
I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem:
Given $n$ in binary, output a prime $p > n$.
I'm both curious about specific ...
5
votes
0
answers
164
views
Can Iterative Compression lead minimization NP-hard problem to both in low complexity and good approximation?
The breakthrough theory of iterative compression introduced by Reed, Smith and Vetta [1] can give positive answers to a number of open problems of parameterized complexity of several important NP-hard ...
5
votes
0
answers
65
views
Interpolating the Tutte polynomial at the values of two hyperbolas
In a MO question
basically I asked when the Tutte polynomial of planar graph
can be uniquely determined by the polynomially computable values at the special points
and at the two hyperbolas. The ...
5
votes
0
answers
150
views
Complexity of edge coloring graphs with $\Delta(G) \ge n/3$
Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices.
What is the complexity of edge coloring ...
5
votes
0
answers
153
views
Evidence of non P-hard problems that require polynomial space?
It is admitted that a $\mathsf{P}$-complete problem requires polynomial space and thus cannot be efficiently parallelized. One purpose of these problems is that they can be used to 'defeat' an (...
5
votes
0
answers
386
views
Approximate c-chromatic number, each color class is P4-free (cograph)
The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
5
votes
0
answers
132
views
Is minimum weight simple cycles through specified vertics fixed parameter tractable?
The problem formulation is as follows:
Input: Undirected graph $G=(V,E)$, a set of vertices $S\subseteq |V|$, a weight function $w:E\to \mathbb{R}$ and a threshold $T\in \mathbb{R}$.
Parameter: $|S|=...
5
votes
0
answers
293
views
Sketch of Razborov's paper "On the method of approximations"
(The following question has bothered me for many years.) Razborov seems to have obtained some of the strongest/award winning lower bounds on circuits found in the field over many years, largely ...
5
votes
0
answers
329
views
Weight enumerator of a binary linear code
The weight enumerator polynomial of a $(n,k)$ binary linear code $\mathcal{C}$ is defined as
$$WE(\mathcal{C}) = \sum_{i=0}^{n}WE_{i}(\mathcal{C}) x^{i}$$
where $$WE_{i}(\mathcal{C}) = \#\{c\in\...
5
votes
0
answers
156
views
Multiple output $AC^0$ circuits?
A naive question perhaps: are there any results/references about $AC^0$ circuits with multiple outputs? Namely, I'm interested in the natural generalization of the Min-$AC^0_d$ problem (find a circuit ...
5
votes
0
answers
278
views
Big O notation for "modulo a polynomial"
Is there a notation that would be like the Big O notation (let's say Big P), but with the following definition:
$f=P(g)$ if there exists a polynomial p such that for n large enough, $f\leq p(g(n))$?
...
5
votes
0
answers
253
views
Is Solomonoff Induction in $\mathsf{P/poly}$?
Consider any language $L$. Define $s(L) \in {\lbrace 0, 1 \rbrace}^\omega$ (an infinite sequence of bits) by the recursive formula
$$s(L)_n=\chi_L(s(L)_{<n})$$
Here $\chi_L$ is the characteristic ...
5
votes
0
answers
172
views
Real-time countable vs fully time-constructible
Real-time countable functions were used in time hierarchy theorem in the papers of Hartmanis and Stearns (Theorem 9, 9.1 ...) and also of Hennie and Stearns (Theorems 3, 5, 7 ...). Now it is a "...
5
votes
0
answers
242
views
Non-uniform average-case complexity of NP
It is conjectured that NP-complete problems are hard not only in the worst case but also in the typical case. Formally, given a language $S \in \lbrace 0,1 \rbrace^*$ and for each $n$ a probability ...
5
votes
0
answers
305
views
Are there applications of experimental mathematics in TCS?
In recent years there have been major, diverse, sometimes surprising advances in experimental mathematics [1] for a variety of sophisticated uses such as developing/deriving exact formulas, theorem ...
5
votes
0
answers
408
views
Sparse Boolean Function and Other Boolean Functions
Let $s$ be a Sparse boolean function $s:\{0,1\}^{n}\rightarrow \{0,1\}$ such that $|s^{-1}(1)| \leq 2^{n\delta}, 0 < \delta <1$
The majority function $MAJ_{n}$ takes value 1 if and only if the ...
5
votes
0
answers
2k
views
Bounded Post Correspondence Problem NP-Complete Proof
I'm looking for a simple proof that shows that the Bounded-PCP problem belongs to NP-Complete as many text books say so.
It is clear to me that the problem is decidable but I cannot find any reduction ...
5
votes
0
answers
276
views
Reduction from planar bounded NCL to a static puzzle game
I call Fill3 the following simple game: the input is a $n \times n$ grid;
every cell of the grid has a type: OR, AND, CHOICE, FANOUT and FIXED and can be rotated 0,...
5
votes
0
answers
141
views
Succinct graphs with ability to perform random walk
Suppose I have an exponentially large graph $G$ ($|G|=2^n$) supplied with an efficient (of size $poly(n)$) randomized circuit $C_G$ implementing the random walk on $G$ - that is, $C_G$ takes a vertex ...
5
votes
0
answers
147
views
What is the relationship between $\mathsf{L}$ reductions and $\mathsf{NC}$ reductions?
The $\mathsf{P}$-complete problems can be considered "inherently sequential". $\mathsf{P}$-completeness may be defined using either $\mathsf{NC}$ reductions or $\mathsf{L}$ reductions.
Since $\mathsf{...
5
votes
0
answers
201
views
Logic capturing automorphism-invariant $\mathsf{AC^0}$ properties
Q1. Is there a logic that is computable in polynomial-time which contains all order-invariant properties computable in smaller classes like $\mathsf{AC^0}$ (or $\mathsf{TC^0}$)?
Motivation
As you ...
5
votes
0
answers
335
views
Complexity of balanced graph partition problem
Wagner and Wagner, in "Between min cut and graph bisection" (MFCS 1993), studied a variant of minimum bisection problem where we seek a cut with minimum size such that each partition has at least $\...
5
votes
0
answers
205
views
Is there an interpretation of the degree of the polynomial computed by the arithmetization of a boolean formula?
If I understand this correctly, arithmetizating a formula is a way of "interpolating" a polynomial in such a way that polynomial evaluated on 0's and 1's corresponds to "unsatisfiable" if it is a root,...
5
votes
1
answer
1k
views
Optimality of Greedy algorithm for minimization Knapsack Problem
Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized.
The greedy ...
5
votes
1
answer
153
views
Problems which will be in $NC$ if fixed dimension Linear Integer Programming in $NC$
We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
4
votes
0
answers
130
views
Is there a 'mathematical program' to separate P from BQP?
This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999).
Usually, such programs are marked by long and ...
4
votes
0
answers
73
views
Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?
Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
4
votes
0
answers
284
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
4
votes
0
answers
110
views
$\mathsf{NL}$ vs. $\mathsf{AC}^1$
It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem PATH belongs to $\mathsf{AC}^1$).
Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\...
4
votes
0
answers
322
views
Complexity of Computing Shannon Entropy
It is my understanding that the necessity of numerical precision can be an obstacle when trying to show a decision problem's membership in a particular complexity class. For example, I believe it is ...
4
votes
0
answers
149
views
(PCP theorem) Any natural decision problem defined in the format of PCP-verifiers?
Is there any natural decision problem that "trivially fits" the definition of a PCP-verifier? I mean, a problem precisely defined as follows: given a set of constraints (each one depending ...
4
votes
0
answers
155
views
What is the intuition behind P/qpoly=P/poly?
I very much struggle to understand the qualitative differences between anything/qpoly. For exampe we read at Watrus that
BQP/qpoly essentially are the decision problems that are solved by
polynomial ...