Most Popular
1500 questions
23
votes
3 answers
How much would a SAT oracle help speeding up polynomial time algorithms?
Access to a $SAT$ oracle would provide a major, super-polynomial speed-up for everything in ${\bf NP}-{\bf P}$ (assuming the set is not empty). It is less clear, however, how much would $\bf P$ benefit from this oracle access. Of course, the…
Andras Farago
- 11,396
- 37
- 70
23
votes
3 answers
Generalizing the "median trick" to higher dimensions?
For randomized algorithms $\mathcal{A}$ taking real values, the "median trick" is a simple way to reduce the probability of failure to any threshold $\delta > 0$, at the cost of only a multiplicative $t=O(\log\frac{1}{\delta})$ overhead.
Namely, if…
Clement C.
- 4,461
- 29
- 51
23
votes
1 answer
Knot Recognition as a Proof of Work
Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion.
Is it possible to use a Decision problem in Knot Theory such as Knot recognition and make…
Joshua Herman
- 1,661
- 17
- 38
23
votes
0 answers
$\Delta = 57, d=2$ Moore Graph
I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years.
You may recall that Hoffman and Singleton proved that the only Moore Graphs [:…
Konstantinos Koiliaris
- 836
- 1
- 8
- 17
23
votes
1 answer
Energy considerations on computation
In order to check my understanding, I would like to share some thoughts about energy requirements of computation. This is a follow up to my previous question and might be related to Vinay's question about conservation laws.
It occourred to me that,…
Antonio Valerio Miceli-Barone
- 2,111
- 15
- 21
23
votes
6 answers
Curriculum: Logical/Formal Methods in Security
At present I teach a small course (Four two hour lectures at the Masters level) on Logical Methods in Security, though the title Formal Methods in Security might be more apt. It covers briefly the following topics (with associated logical…
Dave Clarke
- 16,666
- 3
- 60
- 106
23
votes
2 answers
What was the original intent for the creation of Lambda calculus?
I've read that initially Church proposed the $\lambda$-calculus as part of his Postulates of Logic paper (which is a dense read). But Kleene proved his "system" inconsistent after which, Church extracted relevant things for his work on "effective…
PhD
- 5,305
- 5
- 25
- 40
23
votes
2 answers
Are shift-chains two-colorable?
For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.
For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.
A $k$-uniform hypergraph ${\mathcal H}\subset [n]$ is called a shift-chain if…
domotorp
- 13,931
- 37
- 93
23
votes
4 answers
Can typed lambda calculi express *all* algorithms below a given complexity?
I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming larger as the expressiveness of the type system…
jkff
- 8,941
- 3
- 23
- 33
23
votes
2 answers
Best current space lower bound for SAT?
Following on from a previous question,
what are the best current space lower bounds for SAT?
With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a binary worktape alphabet.
A constant additive term…
András Salamon
- 19,000
- 3
- 64
- 150
23
votes
5 answers
EXPSPACE-complete problems
I am currently trying to find EXPSPACE-complete problems
(mainly to find inspiration for a reduction), and
I am surprised by the small number of results coming up.
So far, I found these, and I have trouble expanding the list:
universality (or…
Denis
- 8,843
- 28
- 55
23
votes
4 answers
Social choice, arrow's theorem and open problems ?
Last few months I started to lecture myself on social choice, arrow's theorem and related results.
After reading about the seminal results, I asked myself about what happens with partial order preferences, the answer is in the paper of Pini et al.:…
Sylvain Peyronnet
- 3,063
- 1
- 18
- 29
23
votes
2 answers
Are there local maxima in the number of moves required to solve a Rubik's Cube?
Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP. As…
Joe Fitzsimons
- 13,675
- 47
- 91
23
votes
1 answer
Languages recognized by polynomial-size DFAs
For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$.
I am interested in languages that are "almost" regular in the sense…
a3nm
- 9,269
- 27
- 86
23
votes
3 answers
Representing OR with polynomials
I know that trivially the OR function on $n$ variables $x_1,\ldots, x_n$ can be represented exactly by the polynomial $p(x_1,\ldots,x_n)$ as such:
$p(x_1,\ldots,x_n) = 1-\prod_{i = 1}^n\left(1-x_i\right)$,
which is of degree $n$.
But how could I…
matthon
- 679
- 4
- 11