# Search Results

Results tagged with Search options answers only user 22714
15 results

Questions related to the (computational) complexity of solving problems

Each element in the sequence is part of the combination or not (a binary choice). Since there are $n$ elements, this gives $2^n$ possible combinations. Using a gray code to iterate over the elements …
answered Jul 21 '17 by orlp
Trivial arbitrarily hard example based on the existence of an one-way function $f : \mathbb{N}^k \to \{0, 1\}$. The problem: Given a set $S$ of size $n$, can we choose a tuple $t$ formed from $k$ …
answered Oct 1 '18 by orlp
Your question is ill-defined, and it's precisely that that I believe to be your misunderstanding. There isn't an inherent cost in Landau notation, or any complexity analysis measure for that matter. …
answered Feb 7 '18 by orlp
Suppose that you have a CNF formula $x$ with input size $n$, and that you can solve $\text{SAT}$ in $O(n^c)$ time for some constant $c$. We construct a new formula $y$. For each clause $l_i$ in $x$, …
answered Dec 2 '18 by orlp
A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the origi …
answered Apr 22 by orlp
You can solve this problem in polynomial time. For simplicity let's assume the DFA has a single accepting state. If it has multiple you can just run this algorithm for each accepting state until you r …
answered Feb 24 by orlp
Counterexample: $f(n) = 2^n$. Then $f(2n) = f(n)^2$.
answered Jan 16 by orlp
This problem is exactly solved by the k-d tree, which organizes points in $k$ dimensions with logarithmic lookup time.
answered May 4 '17 by orlp
It's undecidable because a law book can include arbitrary logic. A silly example censorship law would be "it is illegal to publicize any computer program that does not halt". The reason results for …
answered Nov 27 '18 by orlp
In the Sedgewick-Bentley talk "QUICKSORT IS OPTIMAL" they give an (informal) proof that Quicksorts average case is optimal. So the average case lower bound for sorting is $\Omega(n\lg{n})$.
answered Apr 11 '15 by orlp
From your pastebin, here is the first place you go wrong: unsorted1 = unsorted2 = [randint(1, 99) for _ in range(count)][:] Here you assign unsorted1 and unsorted2 to point to the same list. So whe …
answered Jun 23 '18 by orlp
As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A[i] = 4A[j] = 5A[k]$. We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A[i]$ can on …
answered Jul 16 by orlp
Then it yields that $SAT \in P$ which itself then follows that $SAT \in TIME(n^k)$. Sure. As stands, we are able to do reduce every language in $NP$ to $SAT$. Therefore, $NP \subseteq TIME(n^ … answered Apr 25 by orlp Note that there's always a prime between$p$and$2p$for any$p$thus we can eliminate$n$as a complexity parameter, as for any non-trivial instance we have$n < p$. The complement (there exists a … answered Apr 7 by orlp The crucial data structure here is an interval tree, that can be pre-computed at compile time, which has a complexity of$O(\log n + k)$to find all$k\$ ranges that contain a certain point, assuming t …
answered Feb 7 '18 by orlp