The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [exp-time-algorithms]

The tag has no usage guidance.

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
20
votes
0answers
898 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 ...
16
votes
0answers
272 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, ...
16
votes
0answers
426 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 ...
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 ...
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 ...
8
votes
0answers
102 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
0answers
230 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 ...
3
votes
0answers
809 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 ...
3
votes
0answers
243 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_{...
2
votes
0answers
87 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
46 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 ...
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) ...
1
vote
0answers
198 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). ...
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). ...