Questions tagged [complexity]
The complexity tag has no usage guidance.
75
questions
-1
votes
0answers
42 views
Equivalence of XML queries
$\textbf{Problem statement:}$ Given a set of tree patterns $\{P,P_1,...,P_k\}$ where each $P_i$ has the same topology as $P$ (i.e. $P_i$ and $P$ have the same sets of nodes and edges excepting the ...
9
votes
1answer
111 views
Validity problem of intuitionistic two-variable logic
The two-variable fragment $\mathrm{FO}^2$ consist of those sentences of first-order logic $\mathrm{FO}$ in which precisely two variables occur (e.g. $\exists x \exists y \exists z R(x,y,z)$ is not a ...
4
votes
0answers
173 views
Any problems for which we know the complexity, but no algorithms with the same time?
I suddenly found myself wondering if there are any problems for which the complexity (time or space or anything else) is proven, say to be O(n^2), but for which the best known algorithms are worse ...
3
votes
1answer
83 views
Recursive generic oracles
In
Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide, An oracle builder’s toolkit, Inf. Comput. 182, No. 2, 95-136 (2003). ZBL1025.68041, the authors go through a variety of generic oracles.
...
1
vote
1answer
136 views
Is QMA known to contain Co-NP?
Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
6
votes
1answer
231 views
What is the impact of encodings of sparse structures on the complexity of the model checking problem?
Some preliminaries first.
Consider a purely-relational structure (a.k.a. database) $\mathfrak{A} = (A, R_1^{\mathfrak{A}}, \ldots, R_{|\tau|}^{\mathfrak{A}})$ over some finite signature $\tau = \{ R_1,...
2
votes
1answer
59 views
Relative error estimation of a special type of GapP function
Consider the functions included in the complexity class GapP.
We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly ...
1
vote
0answers
109 views
Deterministic one way communication complexity for message with arbitrary length
Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message.
I have been looking into ...
1
vote
0answers
200 views
What is the computational complexity of the fastest algorithm to compute Jordan canonical form for a matrix
Given a matrix, What is the computational complexity of the fastest algorithm to compute Jordan canonical form for the matrix? suppose the value of elements of the matrix and eigenvalue are complex ...
5
votes
1answer
132 views
Different definitions of grammar complexity
It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
8
votes
1answer
141 views
Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time
Recently I've begun considering how one could generate and solve an $n \times n\times n$ Rubik's cube for $n$ well over 10,000. To solve such a cube is feasible; easily implementable parallelizable ...
3
votes
1answer
114 views
CNF encoding of set cover - NExpTime-completness
Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true.
I ...
9
votes
0answers
139 views
Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?
Planar graphs are 4-colorable.
Determining if a planar graph is 3-colorable is NP-Complete.
A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable.
...
1
vote
1answer
96 views
Is there significance to the ratio of the time it takes to locate a problem's solution over the time it takes to verify the solution?
I believe I have found a problem, the solution to which can be verified in 0 time (the solution can only be located in non-zero time, however). As a result, the ratio of the time required to locate a ...
6
votes
2answers
355 views
On the complexity of a "list" datastructure in the RAM model
I am interested in the complexity of a data-structure equipped with the following operations (similar to a list):
insertion of an element at a given position within the list
deletion of an element at ...
10
votes
1answer
320 views
The theoretical complexity of Go - The state of the art
What are the latest advances in theoretical complexity of Go?
I know some early works about the complexity of Go:
"Go is polynomial-space hard" proved that Go is PSPACE-hard.
"Ladders are PSPACE-...
0
votes
0answers
127 views
Complexity of multi-objective optimization problems
How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?
It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
0
votes
2answers
107 views
Fast algorithm to find pair of triangles with a common edge in a complete graph
Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value $energy$ that is the multiplication of its edge weights. The question is to first find pair of triangles ...
8
votes
4answers
597 views
Constraints on sliding windows
Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.
I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
-1
votes
1answer
179 views
Evidence integer multiplication is in linear time?
After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
11
votes
2answers
3k views
What is a natural problem in theory of computation?
In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]:
Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm.
My question ...
15
votes
0answers
248 views
Does small circuits for a NP-complete problem contradict ETH?
The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
8
votes
1answer
671 views
Is convex optimisation in P?
Consider a convex optimisation problem in the form
$$\begin{align}
f_0(x_1, \ldots, x_n) &\to \min \\
f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m
\end{align}$$
where $f_0, f_1, \...
1
vote
0answers
70 views
Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?
Given
an LSTM $N$ of a given size $A$,
a sentence $S$ with a given number of words $B$,
a Chomsky grammar hierarchy level $C$ in 0-3,
a Chomsky grammar $G$ of level $C$ of size $D$,
A given fixed, ...
2
votes
0answers
70 views
Looking for Research in Cryptographic Computing
I recall reading in college about a nascent research area regarding cryptographic techniques for secure computing, relating to zero-knowledge proofs, but I am having trouble remembering the exact term....
8
votes
0answers
191 views
SAT Solvers and their applications
I've been reading and learning about SAT solvers this week. If they can solve problems with thousands of variable quickly haven't we practically solved ANY problem that can be reduced to it, including ...
5
votes
1answer
430 views
Is there a counterexample to this work?
Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
11
votes
0answers
378 views
Error in paper "Some NP-complete geometric problems"?
The paper in question:
M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems .
This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
6
votes
1answer
216 views
Paths of length $p$ in a Graph, $p$ a prime
I came across the following decision problem, for which I wondered whether anybody of you came across a similar problem and can give me some insight on its nature/complexity.
Given as input a ...
3
votes
0answers
546 views
Implications of resolving $BPP$ vs $PSPACE$
The relationship between the complexity classes $BPP$, $P$, and $NEXP$ is currently undetermined. We know that $P \neq EXP$ by the time hierarchy theorem, but we don't know if $BPP = P$ (as many ...
-1
votes
2answers
1k views
Are these problems in NP class?
${\bf New\ version}$ [Version 1.2]
Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \...
0
votes
1answer
144 views
Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?
Something has been buzzing me recently. It is well-known that $\textbf{PCP}[poly(n), 0] = \textbf{coRP}$, but does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$ ?
I have found a proof for this ...
2
votes
1answer
182 views
Petri net termination
Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example ...
27
votes
2answers
785 views
Formally Verified Complexity Theory
Is there any ongoing project to formally verify the theorems and proofs of complexity theory using a proof assistant like Coq? Are there any boundaries to doing this?
1
vote
1answer
282 views
Complexity of the Schönhage–Strassen algorithm
In the Wikipedia article, the complexity is listed as $O(n \cdot \log (n) \cdot \log (\log (n)))$, where $n$ is the number of bits.
Would the real bound be given by setting $n=\frac{b}{w}$, where $b$...
15
votes
1answer
345 views
Parallel Pebble Game on a Line
In the pebble game on a line there are N+1 nodes labelled 0 through N. The game starts with a pebble on node 0. If there is a pebble on node i, you can add or remove a pebble from node i+1. The goal ...
1
vote
0answers
103 views
How to shrink a very large sparse matrix [closed]
Let $A$ be a matrix where $A \in \mathbb{F}^{n^s \times n^s}$ and $s>2$.
Assume $A$ is a sparse matrix where its rank $\leq n$ and that there is only constant number of non-zero elements in each ...
6
votes
2answers
499 views
Complexity of comparison unary>binary
What is the smallest widely-known complexity class to which
$$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\...
1
vote
1answer
126 views
Why does not the definition of NP problems care about the complexity of guessing? [closed]
I have a question regarding the definition of NP problems. According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time. However, this definition does not ...
6
votes
1answer
136 views
What's the complexity of factoring over a set of generators (say in $GL_2$)?
In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know ...
3
votes
0answers
80 views
Is there any work that relates the liveness of a Petri Net to the complexity of determining coverability?
I'm working on a problem where the formalism appears to be an abstraction of a kind of Petri net, and it is possible to construct an equivalent Petri net from this formalism with the same behavior. ...
15
votes
2answers
2k views
What exactly are the classes FP, FNP and TFNP?
In his book Computational Complexity, Papadimitriou defines FNP as follows:
Suppose that $L$ is a language in NP. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced ...
14
votes
2answers
732 views
Are There Highly Symmetric NP- or P-complete Languages?
Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ...
9
votes
2answers
168 views
Complexity of Computing Lexicographically Minimal Element of Orbit
Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, ...
3
votes
2answers
561 views
Formally proving no algorithm exists [closed]
Are there standard techniques to show that no algorithms exist for given complexity constraints?
For example, consider the following problem. The input is a list of items with exactly one duplicate, ...
1
vote
0answers
162 views
Why does this algorithm not have an exponential complexity? [closed]
In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf
The authors present a PTAS algorithm that can ...
16
votes
2answers
861 views
Does Karp reducibility yield a total order?
Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?
5
votes
1answer
206 views
Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders
Let $X={x_1,...,x_n}$ be a set of variables and $\pi:[n]\rightarrow [n]$ be a permutation of the $n$-element set $[n]=\{1,...,n\}$.
A $\pi$-OBDD is an oblivious, read-once branching program where ...
0
votes
1answer
162 views
Why are these two definitions of PLS equivalent?
In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm.
there is a ...
10
votes
1answer
912 views
2-NEXPTIME-complete problems
We have a problem and we found an algorithm that appear to be 2-nexptime.
I would like to find known 2-nexptime-complete problems in order to find a lower bound.
I found in literature mainly two ...
