Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
-2
votes
0answers
14 views

Are results in complexity theory more of a discovery or invention?

Here by invention I have in mind the following. The result follows from a logic sequence of well established main stream results (baby steps approach of general romantic notion that small iterative ...
0
votes
0answers
21 views

The Edge Cover Equilibrium Problem

Let the Edge Cover Equilibrium Problem be the following: INPUT: a simple undirected graph $G$. OUTPUT: YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
0
votes
0answers
111 views

Why is it difficult for $GCT$ to prove super quadratic lower bound?

We have a quadratic lower bound for the Permanent versus Determinant problem. Why is it difficult for $GCT$ to improve it?
-3
votes
0answers
39 views

Can you build a Turing complete model using only infinitely many OR gates for computation and NOR gates for memory? [closed]

I know NOR can also act as memory other than the NOR boolean function. So my question is can you, if you can build a Turing complete computer using only infinitely many OR gates for computation and ...
22
votes
2answers
803 views

PPAD and Quantum

Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
-5
votes
1answer
89 views

Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
6
votes
2answers
262 views

3SUM Complexity—A special(?) Case

In the paper “Consequences of Faster Alignment of Sequences” by Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
4
votes
0answers
76 views

Complexity of finding the mean of the subset with smallest variance

Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer. Let's consider the following problem $\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\...
6
votes
2answers
414 views

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
32
votes
3answers
2k views

Is this variation of TQBF still PSPACE-complete?

Deciding if a quantified boolean formula such as $\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$ always evaluates to true is a classical PSPACE-complete ...
-2
votes
1answer
121 views

What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different. What evidences are there that $PP$ is in $BQP$? What evidences are there that $PP$ is not ...
1
vote
0answers
42 views

Non-rigid isomorphic structures

In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
2
votes
0answers
203 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 ...
12
votes
2answers
349 views

Complexity relative to the graph of the Busy-Beaver function

This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$. (...
-1
votes
0answers
33 views

Reduce a decision problem to an optimization problem

In this paper, the author shows that finding an edge coloring that minimizes the total sum on a multi-tree is NP-hard. In theorem 3.1, the author does so by reducing from 3SAT. I find his proof quite ...
5
votes
1answer
341 views

Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

Peter Shor commented on this post: years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar. What can we say ...
0
votes
0answers
67 views

Complete problems for dtime

$P$ is the polynomial time class defined as $$\cup_{i=0}^{\infty}DTIME(n^i).$$ which has linear programming as complete problem. Are there complete problems under linear time reductions within each $...
0
votes
0answers
101 views

Can you diagnolize without mentioning simulation?

Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation? The standard diagnolization argument goes: here is a list of ...
15
votes
7answers
3k views

In the neutral zone between polynomial and sub-exponential

What are examples of problems that are known to be sub-exponential, but are known to be non-polynomial, or are not known to be polynomial? EDIT. Here is what I mean by sub-exponential (apologies for ...
3
votes
0answers
77 views

Are there enumerations of machines for all languages in 𝑃 such that there exists a simulator that can efficiently run all the machines enumerated?

From Kozen INDEXINGS OF SUBRECURSIVE CLASSES: "the class of polynomial time computable functions is often indexed by Turing machines with polynomial time counters.... The collection of all (...
5
votes
0answers
171 views

Has there been any development of complexity theory for other Turing degrees than 0?

(I'm not sure if this question is better suited for MathOverflow or here. I'll try here first, and move over to MO later if it appears to be more appropriate.) Complexity theory can be very broadly ...
4
votes
0answers
237 views

Testing emptiness property complexity in Sum of Squares Proof systems

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
-4
votes
1answer
122 views

Is there an algorithm for 3x3 sudokus without backtracking? [closed]

From what I can see on Wikipedia and the Internet at large, all sudoku solving algorithms (including human ones) employ some kind of EXPTIME backtracking search for some sudokus. Are there any SAT ...
7
votes
4answers
977 views

Trees: complexity of counting the number of vertex covers

Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?
79
votes
2answers
25k views

What is the actual time complexity of Gaussian elimination?

In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic ...
35
votes
1answer
1k views

Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis. Conjecture. Let $\mu(k)$ ...
5
votes
2answers
408 views

Bit complexity of integer factorization?

Integer Factorization problem: Given integers $N, M$, find an integer $d< M < N$ that divides $N$. Is it easier to find the value of a single bit? This problem is at least as hard as integer ...
39
votes
3answers
3k views

Is the integer factorization problem harder than RSA factorization: $n = pq$?

This is a cross-post from math.stackexchange. Let FACT denote the integer factoring problem: given $n \in \mathbb{N},$ find primes $p_i \in \mathbb{N},$ and integers $e_i \in \mathbb{N},$ such that $...
17
votes
3answers
860 views

How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes

Teaser Since the problem is longish, here is a special case that captures its essence. Problem: Let A be a deterministic algorithm for 3-SAT. Is the problem of completely simulating the ...
20
votes
5answers
26k views

Direct SAT to 3-SAT reduction

Here the goal is to reduce an arbitrary SAT problem to 3-SAT in polynomial time using the fewest number of clauses and variables. My question is motivated by curiosity. Less formally, I would like ...
8
votes
1answer
321 views

Can we efficiently enumerate the words accepted by a DFA by order of increasing weight?

Fix a deterministic finite automaton $A$ defining a regular language on the alphabet $\Sigma = \{0, 1\}$, and call the (Hamming) weight of a word $w \in \Sigma^*$ its number of $1$'s. Given a length $...
5
votes
2answers
147 views

Topological sorting of a DAG where special vertices have to come in even groups

Consider the following problem. The input is a directed acyclic graph (DAG) $G = (V, E)$, and a subset $V' \subseteq V$ of vertices, which we call special vertices. The question is to determine ...
1
vote
1answer
79 views

Choosing one number from each set so that the sum of squares of each distinct number counts is minimized

Problem is as follows: We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum_{i=1}^n p_i^2$ is minimized where $p_i$ is the number of times ...
2
votes
2answers
139 views

Adjective for: algorithm that outputs its input if it is one of its outputs?

Is there a well established adjective or name for an algorithm such that, given as input any of its own output, always outputs it unchanged? In other words, an algorithm such that it implements a ...
-1
votes
1answer
177 views

Conjecture about ASP reductions between NP-complete problems

$ASP$-complete reductions, introduced by Ueda and Nagao, relate the hardness of computational problems in $FNP$. Basically, $ASP$-reduction is a polynomial time reduction between instances and a ...
8
votes
1answer
301 views

How “hard” is it to maximize a polynomial function subject to linear constraints?

General Problem Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following ...
5
votes
1answer
236 views

Witness verifiable quantum advantage

Update: A slightly different version of this question has been answered here. As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results. ...
39
votes
3answers
2k views

Is there a backup/replacement for the Complexity Zoo?

This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close. The Complexity Zoo webpage (http://qwiki.stanford.edu/index.php/...
1
vote
2answers
66 views

Disjoint subsets problem complexity

Is the decision problem below NP-complete? Given sets $S_1, ... , S_n$, as well as bounds $b_1, ... , b_n$, is it possible to pick pairwise disjoint subsets $U_1, ... , U_n$ such that $U_i \subset ...
1
vote
1answer
106 views

Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, with the essential idea being that of constructing an oracle in ...
0
votes
0answers
26 views

Encrypt an explicit circuit

Suppose we are given a circuit that are promised to be in a fixed class $\mathcal{C}$ (say AC^0). We want to “encapsulate” the circuit such that the resulting circuit computes the same function, while ...
11
votes
1answer
756 views

Enumerating topological sorts of a vertex-labeled DAG

Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a ...
13
votes
2answers
3k views

Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
4
votes
0answers
181 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 ...
20
votes
2answers
1k views

Is feedback vertex set problem is solvable in polynomial time for 3-degree bounded graphs?

Feedback Vertex Set is NP-complete for general graphs. It is known to be NP-complete for degree-8 bounded graphs due to a reduction from vertex cover. The Wikipedia article says that it is poly-time ...
-5
votes
1answer
58 views

We know that X3C is NP-complete with |X|=3q and |C|=m. Is this problem still remains NP-complete if |C|<2q? [closed]

Exact-Cover-by-3Sets (X3C) is NP-complete. If the number of classes i.e. |C|<2q then whether this is version of X3C is NP-complete or not?
11
votes
2answers
239 views

Is there an assumption that implies $P=ZPP$ which is not known to imply $P=BPP$?

There are assumptions that are known to imply that $P = BPP$. For example, if there exists a function in $E = DTIME(2^{O(n)})$ that has circuit complexity $2^{\Omega(n)}$, then $P = BPP$ [1]. Clearly, ...
7
votes
1answer
151 views

Complexity class of efficient streaming algorithms

Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words: $L \in \mathsf{StreamL}$ if there ...
1
vote
0answers
33 views

Efficient algorithm for finding segregators in a directed acyclic graph

Given a directed acyclic graph $G=(V,E)$, we define a $(\alpha,\beta)$-segregator of $G$ to be a subset $S$ of $V$ of size $\alpha$ such that no vertex in $G\setminus S$ has more than $\beta$ ...
3
votes
1answer
121 views

What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)

According to Immerman's Descriptive Complexity diagram, there is a logic called $\mathsf{FO(REGULAR)}$ which captures $\mathsf{NC}^1$. However, I can't find the reference where this logic is defined. ...

1
2 3 4 5
55