Skip to main content

# Tag Info

## New answers tagged time-complexity

0 votes

### What complexity class would this version of generalized chess fall?

But isn't there an upper limit on chess games length? The fifty move rule that says it's a draw if no pawn positions have been changed for the last fifty moves puts an O(n^3) (pieces needed to be ...
1 vote

### How to prove a problem is EXP hard

This is an immediate consequence of the fact that $\text{APSPACE} = \text{EXPTIME}$ (see, for example, here). Specifically, consider a language in $L \in \text{EXPTIME}$, and let $T$ be an alternating ...
• 3,176
3 votes

### Prove that $n$ is a time-constructible function

You essentially need to describe a TM $T$ that given input $x$ computes the binary representation of $|x|$. Note that a full proof does not require you to define every component of the machine ...
• 3,176
3 votes
Accepted

• 1,069
1 vote

### Why would the existence of a sufficiently strong PRNG prove P=BPP?

Let $A$ be a BPP algorithm for the problem, i.e., $A$ runs in polynomial time, uses randomness, and is correct with probability at least 2/3 on every input. Now let's assume we have a PRNG that ...
• 162k
1 vote

### Is $\text{BPP}$ the largest polynomial-time "tractable" complexity class?

The two main candidates are BPP (randomized computation) and BQP (quantum computation). No one knows yet whether quantum computers will feasible, but if they are, BQP is a good candidate for modeling ...
• 162k
1 vote

### Runtime of randomization algorithm to find majority element in an array?

$i$ is the number of tries, and $\frac{1}{2^i}$ is the probability of needing that many tries. We can lay out all outcomes on the table, assign the probability of each outcome, and then sum them all ...
• 11
0 votes

### Why is the time complexity of bidirectional breadth first search still considered O(V + E)?

As the comments say, in the worst case you end up traversing the whole graph. No matter what graph you have, breadth first search is always O(V + E). So it's better to start with O(V + E) and see how ...
• 289
4 votes

### Deducing upper bound for Boolean Circuit size from well-known algorithms

A Turing machine running in time $t(n)$ can be simulated by circuits of size $O(t(n)\log t(n))$; see e.g. https://courses.cs.washington.edu/courses/cse532/04sp/lect05.pdf . More generally, a similar ...
• 1,361
1 vote

### Practical hard 3-sat instances

you could have a look at at Zero-One Designs Produce Small Hard SAT Instances The instances are generated drawing from combinatorial block design and yield instances of up to 100 variables that were ...
• 143
-1 votes

### Up to a certain number of witnesses, say 4

If i need four so-called “witnesses”, then these four “witnesses” together form one real witness. If a problem in NP has an instance with an answer “YES”, then I solve this in two steps. 1. Hire a ...
• 31.1k
-1 votes

### Up to a certain number of witnesses, say 4

Your claim is wrong. Such languages are not necessarily in NP. NP is the class "has at least 1 witness". CoNP is the class "has 0 witnesses" (equivalently: "has at most 0 ...
• 162k

Top 50 recent answers are included