Questions tagged [complexity]
The complexity tag has no usage guidance.
95 questions
0
votes
0
answers
13
views
Regret bound of returned policies
I encountered a proof in the paper Imitation Projected Programmatic Reinforcement Learning that I find puzzling.
In particular, it is Theorem A.2 in the appendix, in the section of Bounding relative ...
3
votes
1
answer
395
views
Does ETH imply P vs NP is decidable?
I have been reading Scott Aaronson's summary paper on P vs NP. In this paper, there was a section about the likelihood of the problem being undecidable (page 28). He mentions a paper that I could no ...
- 59
2
votes
1
answer
194
views
Is $K^t$ complexity closed under composition
Call an increasing function $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ reasonable if $\forall c \in \mathbb{N}, \exists_\infty n, c K^{2n}(n) \leq \alpha (n)$. Where $K^t$ is the time bounded ...
- 341
3
votes
0
answers
104
views
Collapse of query and oracle hierarchies
Let ${\tt QH}$ stand for the Query Hierarchy, defined as the union of all classes ${\tt P}^{{\tt NP}[k]}$, of problems solvable by polynomial time machines making at most $k$ queries to ${\tt NP}$ and ...
- 120
1
vote
0
answers
83
views
Separating disjoint PSPACE-hard sets by NP-separators (and some variants)
I am trying to find some references or arguments for results of the form, where $X,Y$ vary over complexity classes, typically with $X\subseteq Y$, and $A,B$ are disjoint languages that are $Y$-hard:
...
- 171
3
votes
0
answers
95
views
Complexity of chess with 50-move rule
It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
-1
votes
1
answer
116
views
The role of Turing machines in computational complexity [closed]
In the popular book "Introduction to algorithms" by CLRS even though rigorous proofs are given about the complexity analysis of algorithms there is no mention of Turing machines. Instead ...
- 99
0
votes
0
answers
105
views
Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances
I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances.
input and output: input: A satisfiable cnf ...
- 388
3
votes
1
answer
212
views
What’s the complexity of this decision problem with bit shifting?
I’ve been wondering about the computational complexity of a problem that involves bit shifting.
Let me define some notation before I present the problem.
If $\langle{b}\rangle$ is a bitstring ...
- 196
6
votes
3
answers
431
views
What are some examples of decidable Natural Problems outside of EEXP?
I haven't really seen any examples of problems in complexity classes higher then EEXP. What are some examples of some primitive recursive problems outside of EEXP? Ideally with a large number of Es, ...
- 353
4
votes
1
answer
325
views
is SUBEXP contained within PSPACE?, NP?
Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if ...
- 353
0
votes
0
answers
39
views
Hardness of finding minimal subsets that will change the maximum of a univariate polynomial
Given a univariate polynomial of the form $p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all ...
- 11
7
votes
0
answers
86
views
How is FNP defined? Or, is FNP closed under relaxation?
I hope this isn't a dumb question, but I've been driving myself nuts regarding the following.
The definition of $\mathsf{FNP}$ that I've found in many places is the following:
A relation $R(x,y)$ is ...
- 1,214
0
votes
1
answer
107
views
What's the exact complexity of a DFS if we revisit nodes?
By "revisit nodes," I mean if we didn't maintain a set of nodes we have visited. So the sum I'm examining is just the number of paths from a root to a node, across all roots and nodes. We'll ...
- 13
0
votes
1
answer
131
views
Complexity of "opposite" version of a variant of #Positive-2-SAT
In this post ,I introduced a new variant of #Positive-2-SAT .
This version of problem puts restrictions on the inputs of the
#Positive-2-SAT such that we can only choose at max only 2 clauses from ...
- 13
4
votes
1
answer
236
views
Most Matrices are Rigid
The rigidity of a matrix $M\in \mathbb{F}^{n\times n}$ is the minimum number of entries that need to be changed in $M$ to reduce its rank to $r$. Formally, it is defined as:
$$R_{M}^{\mathbb{F}}(r) = \...
- 153
7
votes
1
answer
271
views
Is DFA language inclusion decidable in quasi-linear time? [duplicate]
Given two DFAs $A_1$ and $A_2$, we want to decide whether $\mathcal{L}(A_1) \subseteq \mathcal{L}(A_2)$. Of course, one can compute whether $\mathcal{L}(A_1) \cap \mathcal{L}(A_2) = \mathcal{L}(A_1)$. ...
- 197
3
votes
0
answers
80
views
Extending fagin’s theorem for #P (for arbitary structure)
While i am reading Descriptive complexity of #P functions (Saluja) in theorem 1 he state that #FO coincides #P on ordered structures.
This is a corollary from fagin’s theorem. I have read fagin’s ...
- 139
4
votes
0
answers
58
views
Reference for cost of translating between regular language formalisms
It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO).
The cost (say in size ...
- 9,018
5
votes
0
answers
126
views
Are there well-accepted attempts of people to create complexity classes in continuous time?
I'm not in CS theory, but I've talked to a complexity theorist recently who, in passing, suggested that my research (not really analog computing, but hypercomputation using physical systems in ...
- 121
1
vote
0
answers
259
views
Cheapest Insertion is $2$-approximation for TSP
Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
- 11
9
votes
1
answer
163
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 ...
- 1,244
4
votes
0
answers
181
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 ...
- 59
3
votes
1
answer
104
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.
...
2
votes
1
answer
175
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.)
- 187
6
votes
1
answer
263
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,...
- 1,422
2
votes
1
answer
96
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 ...
- 193
1
vote
0
answers
130
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 ...
- 11
1
vote
0
answers
378
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 ...
- 1,071
5
votes
1
answer
150
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 ...
- 411
8
votes
1
answer
180
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
1
answer
178
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 ...
10
votes
0
answers
161
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.
...
- 109
1
vote
1
answer
97
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
2
answers
421
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 ...
- 820
11
votes
1
answer
711
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-...
- 421
0
votes
0
answers
302
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 ...
- 185
0
votes
2
answers
240
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 ...
- 13
8
votes
4
answers
724
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,002
-1
votes
1
answer
264
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-...
- 13.3k
14
votes
3
answers
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 ...
- 143
16
votes
0
answers
281
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)}$ ...
- 161
10
votes
1
answer
1k
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, \...
- 209
1
vote
0
answers
75
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, ...
- 107
2
votes
0
answers
72
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....
- 473
8
votes
0
answers
229
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 ...
- 81
5
votes
1
answer
457
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 ...
- 13.3k
11
votes
0
answers
397
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 ...
- 275
6
votes
1
answer
240
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 ...
- 61
3
votes
0
answers
829
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 ...
- 199