Computer Science
Profile Activity
Meta user
Network profile
Lieuwe Vinkhuijzen
Summary Answers Questions Tags Badges Bookmarks Bounties Reputation All actions

68 Answers

Votes Activity Newest
1
Self study materials for computational complexity theory
Sep 28 '20 at 20:26
3
Is $EVEN-SAT$ $NP$-hard?
Jul 22 '20 at 18:59
1
3-SAT with negative-literals in each clause
May 21 '19 at 9:20
2
A simple clarification on $\#P$ closure properties
Dec 25 '17 at 10:04
2
How to get the best factor for abstract algorithm that has expected cost?!
Oct 14 '17 at 11:27
2
Equivalence of machine $M$ in $BPP$ and $EXP$
Aug 16 '17 at 16:29
8
What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?
Aug 15 '17 at 13:56
5
What problems are believed to have an efficient algorithm?
Jul 22 '17 at 12:54
1
Why is the lower bound of element uniqueness in $\Omega(n\log n)$?
May 8 '17 at 10:37
5
Could Subset Sum Problem Be Solved In linear Time Using Logarithmic Space?
Apr 16 '17 at 9:28
20
Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?
Apr 12 '17 at 17:23
3
Given a function and its complexity, what is the complexity of its circuit?
Mar 31 '17 at 8:55
5
Why are Chess, Mario, and Go not NP-complete?
Feb 23 '17 at 12:32
5
Running time of algorithms that sometimes loop forever
Jan 2 '17 at 18:54
5
Why is the word “calculus” used to describe systems of logic and computation?
Dec 31 '16 at 15:13
3
Given a string, is it possible to determine which hashing algorithm has produced it, if any?
Dec 30 '16 at 18:22
18
Time complexity of addition
Dec 30 '16 at 14:56
1
Why an ARM processor with 32 bits address bus can address 4 billion different bytes?
Dec 30 '16 at 14:49
3
Justify the following running time
Dec 29 '16 at 22:13
1
How these two Turing machine problems are different in terms of their decidability?
Dec 19 '16 at 21:08
3
What are applications of computational models beyond P?
Dec 18 '16 at 16:54
1
Valid actions of Reductions to NP-Completeness
Dec 13 '16 at 1:27
4
Doesn't a quantum algorithm being deterministic contradict the superposition principle?
Dec 2 '16 at 12:14
5
“P may collapse” vs. Time hierarchy theorem
Nov 27 '16 at 12:18
1
Does applying Hadamard gate is identical to applying a measurement gate that is perpendicular to the current qubit state?
Nov 15 '16 at 19:11
0
Parameterized vertex cover on $r$-regular graphs
Sep 30 '16 at 10:11
4
How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically?
Sep 29 '16 at 22:34
8
Why can't we exploite finiteness to prove incompleteness in NP?
Sep 21 '16 at 17:51
2
Proving complexity by reduction using strongly NP-hard problem
Sep 13 '16 at 16:13
38
Is the halting problem decidable for pure programs on an ideal computer?
Sep 13 '16 at 6:51
1
2 3