Questions tagged [exp-time-algorithms]
The exp-time-algorithms tag has no usage guidance.
52
questions
5
votes
1answer
172 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
0answers
81 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
vote
0answers
45 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
1answer
68 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 ...
14
votes
1answer
327 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
1answer
258 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 ...
3
votes
1answer
275 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 ...
-3
votes
1answer
112 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)?
8
votes
0answers
100 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 ...
5
votes
2answers
191 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 ...
3
votes
1answer
131 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$...
16
votes
0answers
271 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, ...
5
votes
1answer
120 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 ...
13
votes
0answers
188 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 ...
3
votes
1answer
130 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)...
4
votes
1answer
192 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 ...
10
votes
1answer
238 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=...
28
votes
2answers
3k 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 ...
4
votes
2answers
285 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 ...
8
votes
3answers
260 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 ...
7
votes
1answer
258 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, ...
7
votes
1answer
335 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 ...
4
votes
1answer
87 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-...
1
vote
0answers
42 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) ...
16
votes
0answers
425 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 ...
5
votes
0answers
225 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 ...
0
votes
0answers
70 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).
...
5
votes
1answer
829 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
3answers
4k 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.
...
0
votes
1answer
208 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 ?
4
votes
1answer
711 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 ...
12
votes
2answers
347 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?
3
votes
0answers
806 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 ...
2
votes
1answer
265 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 ...
11
votes
1answer
437 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 ...
10
votes
2answers
411 views
Hardness of a subcase of Set Cover
How hard is the Set Cover problem if the number of elements is bounded
by some function (e.g, $\log n$) where $n$ is the size of the problem instance. Formally,
Let $\mathcal{U}=\{e_1, \cdots, e_m\}$...
20
votes
0answers
893 views
Exact algorithm for NAE-3SAT
The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal.
The problem is NP-complete. One ...
9
votes
2answers
372 views
Exact exponential-time algorithms for 0-1 programs with nonnegative data
Are there known algorithms for the following problem that beat the naive algorithm?
Input: matrix $A$ and vectors $b,c$, where all entries of $A,b,c$ are nonnegative integers.
Output: an ...
14
votes
0answers
293 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 ...
10
votes
2answers
575 views
Exact exponential-time algorithms for 0-1 programming
Are there known algorithms for the following problem that beat the naive algorithm?
Input: A system $Ax \le b$ of $m$ linear inequalities.
Output: A feasible solution $x^*\in \{0,1 \}^n$ if ...
3
votes
0answers
242 views
Slightly Faster Exponential Algorithm for Integer Programming with Multi-linear Variables
Integer programing is one of the most narutal optimization tools.
As an analogy of DNF or CNF in the Boolean function theory, we can consider the following equation.
$x_{1}x_{2}x_{3}+$ $x_{3}x_{4}x_{...
13
votes
1answer
792 views
Exact algorithms for non-convex quadratic programming
This question is about quadratic programming problems with box constraints (box-QP), i.e., optimisation problems of the form
minimise $f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x} + \mathbf{c}^T \mathbf{...
10
votes
2answers
340 views
Subset Numbering
Fix $k\ge5$.
For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$.
We would like this labelling to satisfy the following ...
18
votes
3answers
1k views
Solving Superstring Exactly
What is known about exact complexity of the shortest superstring problem? Can it be solved faster than $O^*(2^n)$? Are there known algorithms that solve shortest superstring without reducing to TSP?
...
44
votes
4answers
12k views
Approximation algorithms for Metric TSP
It is known that metric TSP can be approximated within $1.5$ and cannot be approximated better than $123\over 122$ in polynomial time.
Is anything known about finding approximation solutions in ...
3
votes
4answers
2k views
Finding cliques in a big graph
I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques ...
1
vote
1answer
657 views
Learning about EXPTIME and EXPSPACE
I'd like to know some good starting points (such as books, papers, lecture notes, etc.) on EXPTIME and EXPSPACE. I'd like to learn more about these two topics, but I'm not sure what the best approach ...
1
vote
0answers
197 views
Upper bound for set cover with respect to m that is better than trivial when $n \ge 3m$
Does anyone know of an upper bound for Set Cover $(\mathcal{U}, \mathcal{S}, k)$ with respect to $m=|\mathcal{S}|$ that is better than trivial when $n =|\mathcal{U}|$ is at least $3m$?
(Set cover).
...
3
votes
3answers
1k views
Pseudo-polynomial time algorithms
Consider the following algorithm:
Given a natural number as input, say $N$, the algorithm runs a loop (in which the algorithm does $O(1)$ time operations) $N$ times. Now, by definition of time ...
9
votes
2answers
5k views
Time complexity of Held-Karp algorithm for TSP
When I looked through "A Dynamic Programming Approach to Sequencing Problems" by Michael Held and Richard M. Karp, I came up with the following question:
why the complexity of their algorithm for TSP ...
