Ariel's user avatar
Ariel's user avatar
Ariel's user avatar
Ariel
  • Member for 9 years, 2 months
  • Last seen this week
  • Israel
38 votes

in O(n) time: Find greatest element in set where comparison is not transitive

37 votes

Is it possible to write an AND gate using XOR gates?

31 votes
Accepted

Can a computable function converge to an uncomputable number?

28 votes

What is an extremely basic asymmetric cipher that I can present at the pub?

26 votes

Why is deep learning hyped despite bad VC dimension?

25 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

14 votes

Why do public key systems involve private keys?

11 votes
Accepted

To what extent is my interpretation of computable numbers correct?

11 votes
Accepted

Deformation of algorithms

10 votes
Accepted

Does there exist an equivalent arithmetic circuit for each computable function?

10 votes

How to prove that a language is not regular?

10 votes

Turing machine + time dilation = solve the halting problem?

9 votes
Accepted

Proof of non-regularity, based on the Kolmogorov complexity

9 votes

Better results for minimum vertex cover algorithms

9 votes
Accepted

Why does P/Poly can also receive bad advice?

9 votes

Why does the square root of n! grow exponentially faster than exponential functions?

9 votes
Accepted

Why doesn't playing audio stop other tasks?

8 votes
Accepted

Distance-preserving permutations

8 votes
Accepted

Shouldn't every algorithm run in pseudo-polynomial time?

8 votes
Accepted

Is the relation between the input and output of an arbitrary algorithm describable by a mathematical function?

8 votes
Accepted

Prove NP-completeness for union of NP-complete language and language in P

8 votes
Accepted

Is every PSPACE-complete problem complete with respect to logspace reductions?

8 votes
Accepted

Why does the copycat strategy work for two parallel chess games?

8 votes
Accepted

For some $n$, how can we check whether there exists $a,b \in \mathbb{N}$ such that $a^b = n$ in polynomial time?

8 votes

Naive argument that P ≠ NP

7 votes

Problem with the pseudo random number generator One-Time-Pad

7 votes
Accepted

Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?

7 votes

Is squaring easier than multiplication?

7 votes
Accepted

What is the purpose of interpreting elements in the proof of reduction of PCP to validity decidability problem of predicate logic?

7 votes

set of Kolmogorov-random strings is co-re

1
2 3 4 5
10