Questions tagged [exp-time-algorithms]
The exp-time-algorithms tag has no usage guidance.
67
questions
1
vote
0
answers
36
views
Minimum vertex-separators under edge addition
I am trying to prove the following claim.
Let $T$ be a minimum $st$-separator in an undirected graph $G$, and let $x \in T$.
Let $S\neq T$ be a minimal $st$-separator (i.e., not necessarily minimum), ...
- 95
0
votes
0
answers
57
views
Size vs. Time Hierarchy Theorems
I'm struggling with the following idea, but I cannot see where my mistake is.
We know, from the Time Hierachy Theorems, that there are problems that require, say, double exponential time to decide. ...
- 607
0
votes
0
answers
68
views
What is the right notion of reduction for 2EXPTIME?
I've recently been working on some temporal logic problems. In particular, a central result in the field is the fact that realizability for LTL is 2EXPTIME-complete. I've only seen the result quoted ...
- 607
0
votes
2
answers
622
views
Best known algorithm for NEXP-complete problem
What is the best (in time) algorithm for NEXP-complete problems?
Is there an algorithm that solve a NEXP-complete problem in time $2^{o(2^n)}$?
- 1,881
6
votes
0
answers
99
views
Algorithmically determining proof complexity for Frege systems?
I apologize if this falls wildly short of research level - I am just learning the very basics of proof complexity and lack any real logic background.
Let $F$ be a Frege proof system (a finite complete ...
- 161
10
votes
0
answers
141
views
Fastest Known Algorithm to Count Acyclic Orientations in a Graph
Given an undirected graph $G$, an acyclic orientation of $G$ is choice of orientation for each edge of $G$ (turning each edge into an arc) such that the resulting directed graph has no directed cycles....
- 484
4
votes
0
answers
169
views
Fastest Known Algorithm for $k$-Dimensional Matching and $k$-Exact Cover
Given a $k$-uniform hypergraph $G$ (i.e., each edge of $G$ contains precisely $k$ vertices) on $n$ vertices, the $k$-Exact Cover problem is the task of deciding if there exists $n/k$ edges in $G$ ...
- 484
1
vote
0
answers
219
views
anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
- 1,050
33
votes
12
answers
5k
views
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:
The original algorithms,...
- 331
3
votes
0
answers
141
views
If $\sf{E} = \sf{NE}$. Then $\sf{NP}-{P}$ contains no sparse sets [closed]
I am reading "The Complexity Companion" by Hemaspaandra & Ogihara, I have a question about lemma 1.21.
In its proof, they suppose $L$ is some sparse language in $\sf{NP}$ ($||L^{=n}||&...
- 139
8
votes
1
answer
346
views
On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$
It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses.
Being $s_k=\...
- 6,715
2
votes
0
answers
168
views
Time complexity of Succinct-CVP
I want to know what is the best known lower time complexity of Succinct-CVP?
The succinct version of many P-complete problems are EXP-complete and Succinct-CVP is EXP-complete too (It is because of ...
- 327
-1
votes
1
answer
241
views
Does two-sided error have more capability than one-sided error?
From $P=RP$ extrapolation we might think $EXP=REXP$.
What evidence do we have $BPP\subseteq REXP$?
What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?
- 12.6k
15
votes
2
answers
2k
views
NP-hard problems with very fast exponential-time algorithms
NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare.
Is any fact like
"For any constant $\epsilon>0$ there is an NP-hard 'natural' ...
- 4,828
6
votes
1
answer
253
views
What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?
It is known that computing $(\sqrt 2 -\epsilon)$-approximation for VC is NP-hard and that UGC implies that even a $(2 -\epsilon)$-approximation is hard.
There is also a parameterized algorithm for ...
- 9,408
5
votes
1
answer
221
views
Correctness of AKS algorithm for shortest vector problem
Short question
In the end of section 1 of Regev's notes about the AKS algorithm for SVP, why is the following true?
for each such $i$,$y_i− x_i$ remains $w$ with probability $1/2$ or otherwise ...
2
votes
0
answers
93
views
A question about UE
Much has been written about the class UP see related (even more in literature)
example question here. Much is understood about the class UP, and its place in collapsing the PH too. UP has a played ...
- 1,081
1
vote
1
answer
229
views
Asymptotic time required to simulate a Turing machine M for k steps
Problem: Given an encoding of a Turing machine M and a natural number k as input, find the output of M (given a blank tape) after k steps.
Wikipedia's page on EXPTIME-complete says it takes O(k) time ...
0
votes
1
answer
89
views
Question on deduction that a certain problem requires exponential space
My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space.
Regular expressions with squaring are like ordinary ...
- 1,987
13
votes
1
answer
512
views
The problem of deciding whether a monotone CNF implies a monotone DNF
Consider the following decision problem
Input: A monotone CNF $\Phi$ and a monotone DNF $\Psi$.
Question: Is $\Phi \to \Psi$ a tautology?
Definitely you can solve this problem in $O(2^n \cdot \...
-2
votes
1
answer
566
views
Why is it a mystery if PSPACE ?= EXPTIME?
It seems obvious to me that $PSPACE \neq EXPTIME$. I, however, do not believe that my seemingly obvious logic would not be picked up by more intelligent people if it was so simple, so I'm assuming ...
7
votes
2
answers
416
views
Most general setting for fine-grained exponential-time complexity classes?
Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine.
By the Hennie-Stearns theorem, the same functions are computable in ...
- 548
-3
votes
1
answer
213
views
Proof: PTIME not equal EXPTIME [closed]
Can someone give me the name of a paper where this is proved or maybe just prove it here (if it's easy enough)?
- 207
8
votes
0
answers
114
views
Reference for a circuit lower bound for slightly superexponential time
It is known that $EXP$ doesn't have circuits of size $n^k$. On the other hand proving $10 n$ lower bound on circuit size for $E$, $NE$ or even $E^{NP}$ is a known open problem.
My question is ...
- 829
5
votes
2
answers
242
views
Oracle comparing $EXP$ with $UP$
Heller (Theorem 6) gave an oracle relative to which $NP=EXP$, and Homer & Selman gave an oracle relative to which $P=UP$ and $\Sigma_2^P=EXP$.
Beigel, Buhrman, Fortnow (freely available author's ...
- 12.6k
3
votes
1
answer
147
views
Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?
We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$...
- 31
17
votes
0
answers
373
views
Intermediate problems between PSPACE and EXPTIME
Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves.
Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, ...
- 8,473
5
votes
1
answer
150
views
Reference request: complexity of $k$-partite $k$-SAT
Let's consider following variation of $k$-SAT that I will call $k$-partite $k$-SAT:
given $n$ variables that are divided into $k$ groups and a $k$-SAT formula $\phi$ such that each clause has literal ...
- 829
13
votes
0
answers
213
views
Parameterized Algorithm to Speed up Exact Exponential-time Algorithm
The connection between $c^kn^{O(1)}$ for $c<4$ and exact exponential-time algorithms beating brute-force $O(2^n)$ algorithms has been known for a long time. However, when $c\geq 4,$ there are not ...
user17918
3
votes
1
answer
138
views
Consequences of faster parameterized integer programming
Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space.
Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)...
- 12.6k
4
votes
1
answer
275
views
Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?
This question is about subset problems (the solution is a subset of the instance, so trivially enumerable in $2^n \cdot n^c$ time), and the parameter is the solution size, so-called the standard ...
- 2,560
10
votes
1
answer
339
views
EXP-Complete Problems vs Subexponential Algorithms
Does the fact that a problem $A$ is EXP-time complete implies that $A$ is
not in $DTIME(2^{o(n)})$?
I'm aware that by the time hierarchy theorem, $EXP=DTIME(2^{n^{O(1)}})$ is not
included in $E=...
- 1,062
41
votes
2
answers
6k
views
Do any quantum algorithms improve on classical SAT?
Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT )
For comparison, using Grover's algorithm on a quantum ...
- 797
5
votes
2
answers
358
views
Questions regarding SETH
I read about the strong exponential time hypothesis, which states (as far as I understand) that SAT problem cannot be solved in running time $O(2^{\epsilon n})$ for any $\epsilon < 1$, where $n$ is ...
- 59
14
votes
6
answers
495
views
Problems with Unknown Single Exponential Time Agorithms
I'm looking for examples of problems for which it is easy to get algorithms running in time $2^{O(n\log n)}$, or $2^{O(n^c)}$ for some $c>1$ but for which it is not known whether there is an ...
- 1,062
8
votes
1
answer
323
views
Two DFA intersection emptiness connections to SETH & L vs P
(re "fine grained complexity") Wehar has proved that
Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false.
does anyone see any particular key proof difficulty, challenge, ...
- 10.9k
8
votes
1
answer
516
views
Complexity of validity problem for Monadic First Order Logic?
Monadic First Order Logic is FOL with no function symbols, and predicate symbols restricted to arity 1. For this question, let's say that the = symbol is also forbidden. I want to know the complexity ...
- 203
4
votes
1
answer
96
views
Approximate matching in table of integer vectors
Disclaimer: This is my first question on cstheory.stackexchange.com so please be forgiving.
I have a list of M (M is big, more than 1 million elements) vectors of integers. Each vector can contain 0-...
- 141
1
vote
0
answers
45
views
Information about algorithm to generate sequences
I want to make an application for generating a sequence (called S) of items (I), based on conditions (called C).
The Conditions are defined as a property with a 'bonus/reduction'. The total score (T) ...
- 111
15
votes
0
answers
453
views
What is the evidence for average case separation between EXP and NEXP?
There is significant evidence from cryptography that there exist NP-complete problems that are hard in the average case (meaning that e.g. $AvgP \nsupseteq DistNP$). Namely, we have candidate one-way ...
- 2,151
5
votes
0
answers
249
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 ...
- 898
0
votes
0
answers
73
views
Finding exact value with a quotients of products of random values
Sorry for the haphazard title: really not sure what this should be called
Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime).
...
- 149
5
votes
1
answer
3k
views
What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?
What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction? Why?
Details:
http://en.wikipedia.org/wiki/Powerset_construction states that the worst-...
13
votes
3
answers
5k
views
Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?
Do you know of any problems (preferably at least somewhat well known), where, for a practical problem size, an exponential algorithm runs much faster than a best-known polynomial time counterpart.
...
- 313
0
votes
1
answer
221
views
Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms
What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?
- 650
4
votes
1
answer
1k
views
Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers
It is often said that memoization brings the complexity of recursive-descent parsers
from exponential to polynomial. However, I had a hard time finding an example grammar
that triggers the exponential ...
- 376
12
votes
2
answers
407
views
$\overline{SAT} \in NTIME(subexp)$?
Is it possible that $\overline{SAT} \in NTIME(\exp(n^{0.9}))$ ?
Are there interesting consequences of such containment?
Would it contradict the Exponential Time Hypothesis?
- 1,897
3
votes
0
answers
955
views
What's the hardest problem with a non-trivial exact algorithm?
Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough.
I’ve also came across some algorithms which are not practical even for very small inputs, and their ...
- 9,408
2
votes
1
answer
277
views
Design of exact algorithms for non-local hard problems
In the connected dominating set problem (CDS) we are given an $n$-vertex undirected graph, and asked to find the smallest connected subset $S$ of vertices such that each vertex not in $S$ is adjacent ...
- 3,160
12
votes
1
answer
548
views
Computational Model in SETH
Impagliazzo, Paturi and Calabro, Impagliazzo, Paturi introduced Exponential-Time Hypothesis (ETH) and Strongly Exponential-Time Hypothesis (SETH). Roughly, SETH says that there is no algorithm which ...
- 2,162