Skip to main content

New answers tagged

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 ...
Ahmet Ercem Bulut's user avatar
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 ...
Bader Abu Radi's user avatar
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 ...
Bader Abu Radi's user avatar
3 votes
Accepted

Relaxed form of the graph isomorphism problem?

Knowing $\lambda$ definitely helps. Using this mapping, we can order the vertices in $R_1$ and $R_2$ and then perform a linear scan to verify the isomorphism. This should not take more than $O(n\log n)...
codeR's user avatar
  • 1,807
3 votes

Proving that $T(n)=16T\left(\frac{n}{4}\right)+n! \in \Theta(n!)$

We can directly prove the result without using the master method. For $T(n) \in \Theta(n!)$, we need to show $T(n) \in \Omega(n!)$ and $T(n) \in O(n!)$. The first part is easy: $$T(n) = 16T(\frac{n}{...
codeR's user avatar
  • 1,807
3 votes

Proving that $T(n)=16T\left(\frac{n}{4}\right)+n! \in \Theta(n!)$

According to master theorem $T(n)=aT(\frac{n}{b})+ f(n)$, here we get $$a = 16, b = 4, f(n) = n!$$ Thus $$n^{log_{b}a}=n^2$$ As $n! \sim \sqrt{2\pi n}{\left(\frac{n}{\mathbb{e}}\right)}^n$ (Stirling's ...
Chenyang's user avatar
0 votes

Prove n! is fully time constructible

Since the question is about finding a TM that halts after exactly $n!$ steps on inputs of length $n$, here’s a sketch of how that could work. The key identity is $$(n + 1)! = 1 + \sum_{k = 1}^n k! \...
neddo's user avatar
  • 101
1 vote
Accepted

Given that A linear-time reduces to B, what is the solvable relation?

$A$ reduces to $B$ in linear time means that you can formulate an instance of $A$ of size $n$ as an instance of $B$ in $O(n)$ time. So, if you can solve $B$ in $O(n^3)$, for sure you can solve $A$ in $...
SilvioM's user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
D.W.'s user avatar
  • 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 ...
Y Cheng's user avatar
  • 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 ...
Minko_Minkov's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
Manfred Weis's user avatar
-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 ...
gnasher729's user avatar
  • 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 ...
D.W.'s user avatar
  • 162k

Top 50 recent answers are included