# Questions tagged [exp-time-algorithms]

The tag has no usage guidance.

68 questions
Filter by
Sorted by
Tagged with
317 views

### What are some examples of decidable Nautral 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, ...
39 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?
1 vote
37 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), ...
60 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. ...
655 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)}$?
100 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 ...
153 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....
189 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$ ...
1 vote
222 views

### anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
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,...
144 views

172 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 ...
243 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?
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' ...
256 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 ...
230 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 ...
95 views

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 vote
271 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 ...
92 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 ...
540 views

### Is there a W-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 ...