Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [exp-time-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
75 views

Are there any candidate languages in NE but not E?

Let ${\bf E}=\text{DTIME}(2^{O(n)})$ and ${\bf NE} = \text{NTIME}(2^{O(n)})$ Is there any candidate natural language being in ${\bf NE} \setminus {\bf E}$, that is, people believe is ${\bf NE}$ but ...
Eleonora's user avatar
-1 votes
1 answer
187 views

Calculation on Sparsification and critical clauses in SAT

I followed from this question. I need to prove, the final result $s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$ But before prove the final result first I need to prove the $s_k \leq (1 − d/k))s_{\infty}$. ...
S. M.'s user avatar
  • 109
1 vote
1 answer
322 views

Sparsification and critical clauses in SAT

I have been studying the Exponential-Time Hypothesis, ETH, from this paper, there defined $s_k = \inf\{\delta \geq 0 | k\text{-}SAT \in RTIME[2^{\delta n}]\}$. But in that paper's page number 10, I ...
S. M.'s user avatar
  • 109
3 votes
1 answer
75 views

What is the fastest algorithm for computing exact network reliability?

In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i....
Naysh's user avatar
  • 686
6 votes
3 answers
406 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, ...
Colonizor48's user avatar
2 votes
0 answers
47 views

Space complexity of quantum algorithms for Subset sum

As far as I can find there are several quantum algorithms for the Subset sum problem with $2^{n/3}$ running time. Is there an algorithm with $2^{n/3}$ running time that uses much less space?
ivmihajlin's user avatar
1 vote
0 answers
40 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), ...
BBK's user avatar
  • 103
0 votes
2 answers
680 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)}$?
Alexey Milovanov's user avatar
7 votes
0 answers
102 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 ...
Sprotte's user avatar
  • 171
10 votes
0 answers
159 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....
Naysh's user avatar
  • 686
4 votes
0 answers
203 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$ ...
Naysh's user avatar
  • 686
1 vote
0 answers
224 views

anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$?
XL _At_Here_There's user avatar
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,...
TedThomson's user avatar
3 votes
0 answers
146 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}||&...
omega-stable's user avatar
8 votes
1 answer
366 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=\...
Giorgio Camerani's user avatar
2 votes
0 answers
173 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 ...
Mohsen Ghorbani's user avatar
-1 votes
1 answer
246 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?
Turbo's user avatar
  • 12.9k
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' ...
vb le's user avatar
  • 4,828
6 votes
1 answer
269 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 ...
R B's user avatar
  • 9,458
6 votes
1 answer
242 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 ...
Hilder Vitor Lima Pereira's user avatar
2 votes
0 answers
95 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 ...
user3483902's user avatar
  • 1,261
1 vote
1 answer
315 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 ...
ghosts_in_the_code's user avatar
0 votes
1 answer
94 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 ...
StefanH's user avatar
  • 2,077
13 votes
1 answer
555 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 \...
Sasha Kozachinskiy's user avatar
-2 votes
1 answer
601 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 ...
user2894959's user avatar
7 votes
2 answers
436 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 ...
Dan Brumleve's user avatar
-3 votes
1 answer
220 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)?
D. Rusin's user avatar
  • 207
8 votes
0 answers
118 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 ...
ivmihajlin's user avatar
5 votes
2 answers
246 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 ...
Turbo's user avatar
  • 12.9k
3 votes
1 answer
149 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$...
JFK's user avatar
  • 31
17 votes
0 answers
387 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, ...
Denis's user avatar
  • 8,893
5 votes
1 answer
157 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 ...
ivmihajlin's user avatar
13 votes
0 answers
217 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 ...
user avatar
3 votes
1 answer
139 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)...
Turbo's user avatar
  • 12.9k
4 votes
1 answer
295 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 ...
Yixin Cao's user avatar
  • 2,559
10 votes
1 answer
348 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=...
verifying's user avatar
  • 1,072
44 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 ...
Alex Meiburg's user avatar
5 votes
2 answers
373 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 ...
user42109's user avatar
14 votes
6 answers
508 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 ...
verifying's user avatar
  • 1,072
8 votes
1 answer
328 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, ...
vzn's user avatar
  • 11k
9 votes
1 answer
566 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 ...
Dustin Wehr's user avatar
4 votes
1 answer
98 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-...
mnowotka's user avatar
  • 141
1 vote
0 answers
46 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) ...
Michel Keijzers's user avatar
15 votes
0 answers
458 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 ...
Vanessa's user avatar
  • 2,151
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
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). ...
Dave's user avatar
  • 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-...
DaveBall aka user750378's user avatar
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. ...
Ozzah's user avatar
  • 313
0 votes
1 answer
223 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 ?
XORwell's user avatar
  • 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 ...
Wickoo's user avatar
  • 386