# Tag Info

### Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Pivot is unique in the whole array, therefore every sub array containing pivot contains a unique item. Subarrays not containing pivot are the subarrays of the array from start to pivot-1 and the ...
Accepted

### Complexity of satisfiability for relational logic on the booleans

In NP I could guess the disjunctive normal form of the formulas, that would look like $\bigwedge_i R_i(x_1^i, \ldots, x_{n(i)}^i) \land \bigwedge_j \lnot R_j(x_1^j, \ldots, x_{m(j)}^j)$ The question ...
1 vote
Accepted

### What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?

I think there must be some confusion in the problem setting. Given an input of $n$ bits chosen uniformly at random, there is no algorithm to compress it to something whose length is on average ...

### Variant of Bounded Subset Product

The problem can be solved in polynomial time, using dynamic programming. Let $A[k,s]$ be true if there exists a solution to your problem where $f_1 \cdots f_k = s$, or false otherwise. You can fill ...
1 vote

### Complexity of satisfiability for relational logic on the booleans

Nothing much changes. Every relation $R(x_1,\dots,x_n)$ is equivalent to $\exists t_1,\dots,t_m . \varphi(x_1,\dots,x_n,t_1,\dots,t_m)$ for some fresh variables $t_1,\dots,t_m$ (see the Tseitin ...

### Can you compute a majority function of n-bits using an O(n) size circuit?

Interpret each input as a 1-bit number, and sum all the inputs in a binary-tree fashion. At the $i$-th level of the tree you're dealing with numbers with at most $i+1$ bits. Hence the number of gates ...
1 vote

### If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine

The idea is to use the self-reducibility of SAT to construct a search-to-decision reduction. Suppose that we have in our disposal an oracle that solves SAT, and we wish to use it to find a satisfying ...
Accepted

### $NL$ Leaf languages and $PSPACE$

You are omitting some very important details. In the exercise, the Turing machine $N$ is required to halt on all its possible computation paths using exactly $p(n)$ steps, where $n$ is the size of the ...
1 vote
Accepted

### A machine with multiple oracles

The definition of an oracular complexity class is key to answering this question, it is often defined as: $$\mathsf{C^{A}=\bigcup_{L_A\in A}C^{L_A}}$$ But how do we define two oracles? Well the ...
1 vote

### Communication complexity of Dyck language

TL;DR: $n \le C(f) \le n+1$. We can easily prove that $C(f) \ge n$. Consider the set of $x \in \{(,[\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need ...

### Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes

You can't do it in polynomial time (unless P = NP), since it is as hard as the Hamiltonian path problem (consider the special case where you must visit all nodes). One standard approach if you have ...

### Hardness of approximation for Disjoint Group Steiner Tree

As noted in the second paragraph of section 18.2 of these lecture notes, https://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec18.pdf, one can actually assume that the groups are ...

### Prove NP-completeness of deciding satisfiability of monotone boolean formula

IMO, it is intuitive to reduce Vertex-Cover to the problem that you are describing (which will show that the problem you are describing is at least as hard as Vertex-Cover). At the core of the problem ...

### Is there a known polynomial time complexity problem with bad constants?

Another simple one, that turned up in another question. Given a finite set S, sorting any array of elements of S can be sorted in linear time using counting sort (or without any additional storage: By ...
Accepted

### What is the complexity of minimising a convex quadratic function over the integers?

The closest lattice vector problem is NP-hard in the $L_2$ norm. See NP completeness of closest vector problem for a reference to the proof.

### NP completeness of closest vector problem

There is a mismatch in terminology in your question. The problem you specify is known as the shortest vector problem (SVP). You called it the closest vector problem (CVP), but the CVP is something ...

### Reducing euclidean TSP of smaller size to euclidean TSP of bigger size

Here's an idea that doesn't work: Assume K = N-1. Take any node X and create another node X' at a distance epsilon from X, and calculate all the distances to X', then solve the N problem. If that ...

### Parallel Algorithm Analysis: Loops

The work $W(n)$ is the total number of nodes in your computation graph and the span $D(n)$ is the number of nodes on the longest path of that graph. $T_P(n)$ is the runtime of the algorithm using $P$ ...

### Is there a known polynomial time complexity problem with bad constants?

A simple one: Given n chess positions, find an optimal move for each position. The game of chess is finite, so finding an optimal move for any position is O(1), and for n positions it is O(n). With a ...

### Is there a known polynomial time complexity problem with bad constants?

To add another perspective on this: there is a class of problems known as fixed parameter tractable (FPT) which has been studied extensively. In this area of research, one studies problems that, given ...

### True or false? Any finite problem is in P

If by finite problem, you mean a problem with a finite domain, then yes. Such problems are not only in P, but can be done in constant time since you can build a mapping between every possible input ...
Accepted

### Is there a known polynomial time complexity problem with bad constants?

Such algorithms are called Galactic Algorithms.

### ( Soft question ) P vs NP - is such a situation possible?

Consider what happens if I find a polynomial time solution for an NP complete problem. Say a solution taking $n^{100}$ nanoseconds on my computer. For n = 2 that’s $2^{100} \approx 10^{30}$ ...
1 vote

### Dinitz’ algorithm in simple unit-capacity networks

I have no clue about how the values in the other two lemmas are brought up. The how is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized? The answer is $\sqrt n$, ...

### Complexity of simulations in simulations

You can build a universal Turing machine with only 7 states, or only 15 states if you require that the tape store binary symbols. See https://en.wikipedia.org/wiki/Universal_Turing_machine#...

### ( Soft question ) P vs NP - is such a situation possible?

Yes of course it is possible. Everything is possible. Such situations have been rare in mathematics, so I would not bet on it, but we have no way to rule out such a possibility. We do know that ...
1 vote

### Time complexity of search algorithms?

Let $A$ be a comparison-based search algorithm that takes a collection $C$ of $n$ elements and an element $x$ as input and outputs the position of $x$ in $C$, or reports that $x \not\in C$. Let $c(n)$ ...