# Tag Info

5

Yes, because $\mathsf{SAT}$ is $\mathsf{NP}$-complete. Let $L\in\mathsf{NP}^\mathsf{NP}$. This means that there exists $A\in\mathsf{NP}$ such that $L\in\mathsf{NP}^A$. But you can replace any oracle query to the set $A$ with a polynomial-time deterministic computation that uses oracle queries to $\mathsf{SAT}$. Thus, $L\in\mathsf{NP}^\mathsf{SAT}$.

3

It's OK for the certificate to be exponentially long but the space consumption of the verifier must be polynomial in the size of the problem instance (it is not allowed to use space polynomial in the size of the certificate). Conceptually, you can view the certificate as the record of nondeterministic choices made by the nondeterministic algorithm that ...

2

If I remember correctly, there are $\Theta(\frac{n}{\log(n)})$ primes between $n$ and $2n$. Sum them up to get the number of primes up to $2n$, and then we know that $2n$ has $\log(n)+1$ bits. I think if you do the maths it will not end up in $SPARSE$, but I might be wrong here.

2

Lets say you have some certificate of length $s>>poly(n)$, and you are only allowed to store at most $poly(n)$ memory. Assuming you are capable of verifying "chunks" from the certificate of size $poly(n)$ at a time, it really wont matter what $s$ is. Try to think of the following: We iterate through all possible strings of size $poly(n)$ ...

2

Our approach is to finding a recursive formula for time complexity of the code. For each value of $i$, the inner loop runs $\log i$ times. Suppose $T(n)$ is time complexity of given code, so: $$T(n)=T(\frac{n}{2})+\log n$$. At each step we have a $\log i$ cost for inner loop, and outer loop divide our $n$ by $2$. So we get above $T(n)$ that after solving by ...

1

Since ceil(1.5x) = 2 when x = 1, it is a 2-approximation. With the particular value 1.5, we know that ceil (1.5x) is either 1.5x or 1.5x + 0.5, so you could say it is an (1.5x + 0.5) approximation algorithm. There are many problems where the answer x is always small. For example "what is the minimum number of colours to colour this planar graph". ...

1

The usual definition of an $\alpha$-approximation algorithm for a maximization problem is: an algorithm which returns a solution of value at most $\alpha \cdot \mathit{OPT}$, where OPT is the optimal value. In practice, sometimes a more relaxed definition is used: the bound is only required to be $\alpha \cdot \mathit{OPT} + \beta$. This fits your case: if ...

1

Neither of those. For $n>1$, $\lfloor\frac{1}{n}\rfloor=0$. Hence, $\lfloor\frac{1}{n}\rfloor=0=O(0)$. Also, you can easily rule out $\Omega(\log(n))$ since $\log$ is an increasing to infinity, while $\frac{1}{n}$ is a decreasing function.

1

I finally understood what was blocking me. We only need a TM that recognizes an undecidable language so we just have to take a TM $M'$ that recognizes $A_{TM}$ for example and return it when $M$ accepts $w$. We have $L(M') = A_{TM}$ which is undecidable.

1

Maybe try to use Rice' theorem, instead of reducing from $\overline{A_{TM}}$.

1

When you are working on loops like these you can simplify them with sums to count the number of iterations: For example the time it takes on this loop for(int i=1;i<n;i=i*2) { cout<<"hello"; } Can be rewritten as $\sum_{i=1}^{\log(n)}{c}$, where $c$ is the constant time for printing "hello". Hence your double loop can be ...

Only top voted, non community-wiki answers of a minimum length are eligible