# All Questions

12,683 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
2k views

### Consequences of Complete problems for NP intersects coNP

What are the consequences of having complete problems in $NP\cap coNP$?
5k views

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 ...
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 ...
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 ...
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 ...
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, ...