Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Favorites infavorites:mine
infavorites:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with Search options answers only user 22714

Questions related to the (computational) complexity of solving problems

2
votes
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
1
vote
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
2
votes
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
3
votes
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
4
votes
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
1
vote
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
2
votes
Counterexample: $f(n) = 2^n$. Then $f(2n) = f(n)^2$.
answered Jan 16 by orlp
1
vote
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
95
votes
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
2
votes
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
3
votes
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
2
votes
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
55
votes
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
5
votes
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
1
vote
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