Questions tagged [exp-time-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
59 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
43 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
207 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
1answer
84 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 ...
0
votes
1answer
212 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 ?
0
votes
2answers
3k views

Dynamic programming algorithm for NP-complete problem

Hello everybody here is a problem i have approximated but would like to hear your opinion about. Perhaps someone finds a better solution than me :) Given a Graph G with undirected edges: Divide it ...
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). ...
-1
votes
1answer
220 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?
-2
votes
1answer
385 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
162 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)?

1
2