Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [exp-time-algorithms]

The tag has no usage guidance.

63 questions
Filter by
Sorted by
Tagged with
6 votes
0 answers
91 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
128 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....
• 454
3 votes
0 answers
113 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$ ...
• 454
1 vote
0 answers
209 views

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

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$？
• 1,009
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
140 views

• 6,615
2 votes
0 answers
162 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 ...
-1 votes
1 answer
229 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.5k
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
249 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,358
5 votes
1 answer
207 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
130 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
85 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,947
13 votes
1 answer
466 views

• 12.5k
4 votes
1 answer
218 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,530
10 votes
1 answer
319 views

• 1,156
14 votes
0 answers
299 views

### Exponential-time factorization of polynomials

Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field. It is ...
• 4,400