All Questions
12,683
questions
57
votes
18
answers
2k
views
Where and how did computers help prove a theorem?
The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful
in building a conjecture that lead to a theorem,
falsifying a ...
21
votes
4
answers
499
views
Which results in complexity theory make essential use of uniformity?
A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like ...
- 21.5k
141
votes
30
answers
25k
views
Problems Between P and NPC
Factoring and graph isomorphism are problems in NP that are not known to be in P nor to be NP-Complete. What are some other (sufficiently different) natural problems that share this property? ...
17
votes
3
answers
2k
views
Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?
Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ...
- 311
14
votes
1
answer
708
views
What are the historical roots of Milner's bigraphs?
Robin Milner defined bigraphs as a type of graphical structure with graph-like structure but where the nodes can be nested. They generalise process calculi like CCS and the $\pi$-calculus, but Milner ...
14
votes
2
answers
1k
views
How large a treewidth can a tree plus half the edges have?
Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible?
It ...
- 1,394
17
votes
2
answers
687
views
H-free cut problem
Suppose you are given a connected, simple, undirected graph H.
The H-free cut problem is defined as follows:
Given a simple, undirected graph G, is
there a cut (partition of vertices
into two ...
- 1,855
27
votes
4
answers
2k
views
What specific evidence is there for P = RP?
RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
- 18.9k
-1
votes
2
answers
618
views
Minimum spanning tree algorithm. [closed]
Is the following a valid algorithm for finding a minimum spanning tree?
Given a weighted graph with unique weights, remove the all edges that are the highest cost edge in any cycle of the original ...
- 151
12
votes
2
answers
678
views
Simple balanced trees with O(1) concat?
In Purely Functional Worst Case Constant Time Catenable Sorted Lists, Brodal et al. present purely functional balanced trees with O(1) concatenate and O(lg n) insert, delete, and find. The data ...
- 11.2k
30
votes
2
answers
2k
views
Hierarchies in NP (under the assumption that P != NP)
Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem.
Is there any evidence of more ...
- 1,855
26
votes
1
answer
2k
views
Consequences of Complete problems for NP intersects coNP
What are the consequences of having complete problems in $NP\cap coNP$?
- 3,280
65
votes
11
answers
5k
views
What are good references to understanding the proof of the PCP theorem?
I'm familiar with a lot of results that use the PCP theorem (mainly in approximating algorithms), but I've never come across a clear explanation of the PCP theorem (ie, that $\mathsf{NP} = \mathsf{PCP}...
- 1,459
21
votes
2
answers
1k
views
Succinct circuit representation of graphs
The complexity class PPAD (e.g. computing various Nash equilibria) can be defined as the set of total search problems polytime reducible to END OF THE LINE:
END OF THE LINE: Given circuits S and P ...
- 5,961
25
votes
3
answers
1k
views
Graph Isomorphism and hidden subgroups
I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
- 32k
21
votes
1
answer
333
views
A comparison of extractors in terms of tradeoffs between time, randomness and space ?
Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?
- 32k
129
votes
11
answers
12k
views
How hard is unshuffling a string?
A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a ...
- 23.1k
8
votes
1
answer
461
views
Best resources for string searching or pattern matching exercises
I would like to be somewhat good at string searching and pattern matching, could you point me to some good online resources? Exercise problems would be great. Thanks.
17
votes
3
answers
761
views
Are there any known implementations for quantum computing constructs?
Quantum Computation is an active area of research that aims to take advantage of quantum physics (e.g. quantum entanglement) to advance the efficiency capabilities of computers (does not alter the ...
- 2,233
17
votes
1
answer
1k
views
Online transitive closure better than O(N^2) per edge addition
I'm looking for an online algorithm to maintain the transitive closure of a directed acyclic graph with a time complexity less than O(N^2) per edge addition. My current algorithm is like this:
...
- 696
16
votes
6
answers
4k
views
Complexity of the Fisher-Yates Shuffle Algorithm
This question is in regard to the Fisher-Yates algorithm for returning a random shuffle of a given array. The Wikipedia page says that its complexity is O(n), but I think that it is O(n log n).
In ...
- 623
16
votes
1
answer
570
views
Why is it important that the secret is at the end when signing with MD5?
it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?
19
votes
0
answers
513
views
To what extent MSO = WS1S, when adding relations?
[This question has been asked on MathOverflow with no luck a month ago.]
Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma =\{a_1,
\ldots, a_n\}$, I define two ...
- 3,946
24
votes
5
answers
2k
views
What are some career options for someone with a computer scientist master degree?
Other than going fully academic and getting a doctorate/post-doc, or going for a more or less 'standard' job in software development, what are some other career options in the full or semi theoretical ...
35
votes
4
answers
1k
views
Correspondence between complexity classes and logic
I took a class once on Computability and Logic. The material included a correlation between complexity / computability classes (R, RE, co-RE, P, NP, Logspace, ...) and Logics (Predicate calculus, ...
- 863
50
votes
12
answers
4k
views
What is the theoretical basis of imperative programming?
Functional programming has a theoretical basis in lambda calculus and combinatory logic. As someone involved with statistical computing, I find these concepts to be very useful for modeling.
Is ...
- 2,233
8
votes
3
answers
3k
views
Is Deolalikar's 2010 proof that $P \ne NP$ correct?
There was recently a claimed proof that $P \ne NP$. Not long after its publication there were raised some issues with this proof.
So ... is the proof correct or not ? (Please only answer this if you ...
- 863
21
votes
3
answers
567
views
space-bounded TMs and oracles
In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).
Is such a ...
- 433
8
votes
1
answer
199
views
Process modeling with fine-grained notions of location
Is anyone aware of any process algebraic (or related) formalisms that capture fine-grained location information? I'm familiar with ambients and bigraphs, which obviously have a location model, but ...
- 288
10
votes
1
answer
326
views
Generalizing the FFT
Can the divide and conquer nature of the FFT be generalized to other transforms (z Transform, chirp, etc) automatically?
Is there an algorithm that takes in a description of transform (I don't know ...
15
votes
2
answers
1k
views
What is the following variation on Set Cover known as?
What is the following variation on set cover known as?
Given a set S, a collection C of subsets of S and a positive integer K, do there exist K sets in C such that every pair of elements of S lies in ...
- 356
8
votes
1
answer
1k
views
What are some effective heuristics to find the number of Hamiltonian paths in a rectangular grid?
A particular programming problem I came across recently reduces to finding hamiltonian paths in a rectangular grid that would look something like,
...
- 191
13
votes
2
answers
1k
views
What is a good special-case sorting algorithm?
I have a dataset which is a number of objects arranged in a 2-D grid. I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each ...
- 353