Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

781 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
Turbo's user avatar
  • 12.8k
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 ...
Vanessa's user avatar
  • 2,151
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 ...
Dima's user avatar
  • 51
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 ...
gradstudent's user avatar
  • 1,443
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 ...
Ivan Smirnov's user avatar
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 ...
Ramon Bejar Torres's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Alexey Milovanov's user avatar
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(...
Andras Farago's user avatar
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 ...
Vadapalli Adithya's user avatar
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 ...
Kaveh's user avatar
  • 21.6k
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 ...
user avatar
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 ...
Andras Farago's user avatar
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 ...
Martin Zimmermann's user avatar
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 ...
user avatar
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 ...
Thomas Ahle's user avatar
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 ...
Pteromys's user avatar
  • 895
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 ...
usul's user avatar
  • 7,615
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 ...
user avatar
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 ...
joro's user avatar
  • 1,955
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 ...
joro's user avatar
  • 1,955
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 (...
Super8's user avatar
  • 324
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 ...
Peng Zhang's user avatar
  • 1,453
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|=...
R B's user avatar
  • 9,448
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 ...
vzn's user avatar
  • 11k
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\...
Pavithran Iyer's user avatar
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 ...
snikolenko's user avatar
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))$? ...
BastienMob's user avatar
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 ...
Vanessa's user avatar
  • 2,151
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 "...
David G's user avatar
  • 532
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 ...
Vanessa's user avatar
  • 2,151
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 ...
vzn's user avatar
  • 11k
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 ...
Elely's user avatar
  • 309
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 ...
assafisr's user avatar
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,...
Marzio De Biasi's user avatar
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 ...
Marcin Kotowski's user avatar
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{...
argentpepper's user avatar
  • 2,281
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 ...
Kaveh's user avatar
  • 21.6k
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 $\...
Mohammad Al-Turkistany's user avatar
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,...
gabgoh's user avatar
  • 1,548
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 ...
Richard's user avatar
  • 307
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$?
Turbo's user avatar
  • 12.8k
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 ...
Manish Kumar's user avatar
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 ...
Mingda Qiao's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
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 $\...
Alexey Milovanov's user avatar
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 ...
Spencer Compton's user avatar
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 ...
EXPTIME-complete's user avatar
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 ...
Marion's user avatar
  • 183

1
4 5
6
7 8
16