New answers tagged

0 votes

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 ...
gnasher729's user avatar
  • 28.3k
0 votes
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 ...
user1868607's user avatar
  • 2,184
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 ...
D.W.'s user avatar
  • 156k
0 votes

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 ...
D.W.'s user avatar
  • 156k
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 ...
D.W.'s user avatar
  • 156k
2 votes

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 ...
Steven's user avatar
  • 28.2k
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 ...
Yuval Filmus's user avatar
0 votes
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 ...
Steven's user avatar
  • 28.2k
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 ...
Marsh's user avatar
  • 26
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 ...
D.W.'s user avatar
  • 156k
0 votes

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 ...
D.W.'s user avatar
  • 156k
0 votes

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 ...
NaturalLogZ's user avatar
0 votes

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 ...
Benjamin Smus's user avatar
0 votes

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 ...
gnasher729's user avatar
  • 28.3k
2 votes
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.
D.W.'s user avatar
  • 156k
0 votes

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 ...
D.W.'s user avatar
  • 156k
0 votes

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 ...
gnasher729's user avatar
  • 28.3k
0 votes

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$ ...
Stand with Gaza's user avatar
13 votes

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 ...
gnasher729's user avatar
  • 28.3k
7 votes

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 ...
Caleb Stanford's user avatar
0 votes

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 ...
Hunter Livesay's user avatar
26 votes
Accepted

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

Such algorithms are called Galactic Algorithms.
Inuyasha Yagami's user avatar
0 votes

( 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}$ ...
gnasher729's user avatar
  • 28.3k
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$, ...
Pål GD's user avatar
  • 15.5k
2 votes

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#...
D.W.'s user avatar
  • 156k
0 votes

( 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 ...
D.W.'s user avatar
  • 156k
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)$ ...
Steven's user avatar
  • 28.2k
0 votes

Lower Bound on Parity of Boolean Functions

This is false, various construction for computing simultaneously the same function on disjoint sets of variables are discussed in this cstheory.stackoverflow question.
Vladimir Lysikov's user avatar

Top 50 recent answers are included