All Questions
12,298
questions
1
vote
1
answer
1k
views
Removing all but a few cycles in a graph
Let problem $S$ be defined as
Given undirected graph $G$ and a set
of cycles $C_1,C_2, \ldots, C_n$ in G,
find minimum number of vertices that
need to be deleted to remove all
cycles in the ...
- 467
19
votes
1
answer
472
views
Visualizing Unique Games
How would you design a picture to illustrate the unique games conjecture?
This is for a "Current Events" presentation on unique games at the next AMS Joint Meeting and for the booklet that will be ...
- 4,902
12
votes
1
answer
672
views
Using Kolmogorov complexity to establish proof complexity lower bounds?
The motivation for this question is the fact that most n-bit strings are incompressible. Intuitively, we can propose by analogy that most proofs for Tautologies are incompressible to polynomial size. ...
- 20.7k
40
votes
2
answers
4k
views
Semantic vs. Syntactic Complexity Classes
In his "Computational Complexity" book, Papadimitriou writes:
RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the ...
- 16.3k
39
votes
9
answers
4k
views
Optimal greedy algorithms for NP-hard problems
Greed, for lack of a better word, is good. One of the first algorithmic paradigms taught in introductory algorithms course is the greedy approach. Greedy approach results in simple and intuitive ...
- 10.5k
52
votes
20
answers
9k
views
NP-hard problems on trees
Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include ...
- 10.5k
11
votes
2
answers
1k
views
NP-complete variants of undecidable problems?
Examples of bounded $NP$-complete variants of undecidable sets:
Bounded Halting problem={ $(M, x, 1^t)$| NTM machine $M$ halts and accepts $x$ within $t$ steps}
Bounded Tiling={ $(T, 1^t)$| there is ...
- 20.7k
15
votes
3
answers
703
views
Hardness Guarantees for AES
Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.
I wonder whether such kind of provable security exists for ...
- 16.3k
152
votes
39
answers
46k
views
What videos should everybody watch?
Stanford University now has a Youtube channel, with free access to HD video of full courses on everything from dynamical systems to quantum entanglement. More conferences and workshops are ...
1
vote
2
answers
16k
views
What is the k-SAT problem? [closed]
First of all I am of course aware of the wikipedia article: http://en.wikipedia.org/wiki/Boolean_satisfiability_problem
However I still do not understand exactly what the problem is. To demonstrate ...
- 145
7
votes
1
answer
966
views
Graph Theory Fun Problem
Show that in any graph $G$ with min-degree $k$ ($k \geq 1$ duh!) you can find as its subgraph any tree on $k+1$ vertices.
I have not been able to solve the question so far. However, I would like if ...
- 1,953
481
votes
72
answers
180k
views
What papers should everyone read?
This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different.
We all have favorite papers in our own respective ...
7
votes
2
answers
873
views
Universal Turing Machines in "Computational Complexity" by Papadimitriou
The first part of this question has been solved (see comments).
In the book "computational complexity" by Papadimitriou, a Universal Turing Machine is given. But this machine is not concrete, in the ...
Martin
14
votes
2
answers
1k
views
Projective Plane of Order 12
Objective: Settle the conjecture that there is no projective plane of order 12.
In 1989, using computer search on a Cray, Lam proved that no projective plane of order 10 exists. Now that God's ...
- 6,974
4
votes
3
answers
351
views
How can I model this usage scenario mathematically?
I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system.
The system behaves as follows:
clients periodically issue multi-cast packets ...
- 153
-2
votes
1
answer
2k
views
How do I formally describe a rooted, directed, acyclic graph?
I need a formalism to describe the following requirements:
I have a graph comprised of nodes and transitions between nodes
Nodes maybe one of three types, all are sub-classes of a base abstract node ...
- 153
24
votes
6
answers
2k
views
Introduction to spectral graph theory
What are the basic references? Are there any good, high-level surveys of SGT and its applications to CS in general and machine learning more specifically?
4
votes
1
answer
440
views
Is this problem mappable to 3SAT or is it weaker than 3SAT?
Consider a variant of a satisifiability problem.
Given n dimensions (n >= 3, n < 10,000 think of n as large but finite)
The range of each dimension is either an interval over the integers or an ...
- 141
2
votes
2
answers
530
views
Counting complexity of a scheduling problem. [closed]
Let $T={1,…,n}$ be a set of tasks. Each task $i$ has associated a non negative processing time $p_i$ and a deadline $d_i$. A feasible schedule of the tasks consists of a permutation of $n$ elements $\...
Pablo
5
votes
1
answer
3k
views
Turing Machines and Subroutine Simulation
I have been reading Wikipedia as an introduction to Turing machines. I found a reference to John Hopcroft and Jeffrey Ullman, (1979). Introduction to Automata Theory, Languages and Computation (1st ed....
11
votes
2
answers
541
views
Average distortion embeddings
Consider two metric spaces $(X, d)$ and $(Y, f)$, and an embedding $\mu : X \rightarrow Y$.
Traditional metric space embeddings measure the quality of $\mu$ as the worst-case ratio of original to ...
- 31.9k
30
votes
4
answers
1k
views
Are there "small" machines which can efficiently match regular expressions?
It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially ...
- 32.1k
29
votes
3
answers
1k
views
What does one mean by heuristic statistical physics arguments?
I have heard that there are heuristic arguments in statistical physics that yield results in probability theory for which rigorous proofs are either unknown or very difficult to arrive at. What is a ...
- 6,960
7
votes
2
answers
507
views
On the class of the FNP version of the Hamiltonian Cycle problem
This post is linked to: FNP complexity class
Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems are those whose solution can be verified in ...
- 460
9
votes
1
answer
358
views
Metric graph theory database search algorithms
I am (slowly) writing a review of the Handbook of Chemoinformatics Algorithms for SIGACT News. One chapter discusses current software implementations, and the database searches (and other ...
- 6,974
58
votes
3
answers
9k
views
Realizability theory: difference in power between Lambda calculus and Turing Machines
I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering).
Andrej Bauer wrote, here, that some functions are realizable ...
- 2,029
7
votes
2
answers
595
views
SAT Solution Space - Definition of Cluster of Solutions
I'm looking for a formal definition of Cluster of Solutions. My current understanding is the following. Let $x$ be a boolean assignment on $n$ variables. Let $f: \{ 0,1 \} ^n \to \mathbb{N}$ be a ...
- 6,695
4
votes
1
answer
220
views
Optimizing multiplication in a partly commutative semigroup
Let us say I have a semigroup M and its basis B. I know which elements of B commute.
What is the most efficient way to do multiplication in such a semigroup?
Essentially, this is a question of how ...
- 8,721
13
votes
1
answer
531
views
Fast sparse boolean matrix chain product
So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually ...
- 8,721
11
votes
7
answers
1k
views
Quantum Computation - Postulates of QM
I have just started (independent) learning about quantum computation in general from Nielsen-Chuang book.
I wanted to ask if anyone could try finding time to help me with whats going on with the ...
- 1,953
10
votes
1
answer
438
views
Hardness of constrained star system problem?
A star system is a family $F$ of n subsets of n-elements set $S$. A star system is graphical if there is some graph $G(V,E)$ such that $F$ is the family of vertex neighborhoods in $G$. It is $NP$-...
- 20.7k
1
vote
1
answer
299
views
Constraint Satisfaction Problem: Choosing real numbers with certain characteristics
I have a set of n real numbers. I also have a set of functions,
f_1, f_2, ..., f_m.
Each of these functions takes a list of numbers as its argument. I also have ...
- 299
18
votes
2
answers
2k
views
Beginner's Guide to Derandomization
I found the book Pairwise Independence and Derandomization on the subject, but it's more research-oriented than tutorial oriented.
I'm new to the subject of "Derandomization," and as such, I wanted ...
- 16.3k
6
votes
0
answers
151
views
Constraint Satisfaction Problem: Choosing real numbers with variance in a certain range
I have a set of n real numbers. I want to repeatedly choose subsets of k elements such that the variance of these k numbers falls within some specified range, r = [l, u]. Moreover I want to do this ...
- 299
4
votes
3
answers
562
views
FNP complexity class
Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity)
However, that isn't sufficient for me to ...
- 460
3
votes
2
answers
4k
views
Using decision version of TSP to solve optimization version
Given an oracle for solving the decision version of TSP, how would I use this to solve the optimization version of TSP.
This is not a homework assignment, but of general interest. I have been trying ...
- 171
34
votes
2
answers
3k
views
NTIME(n^k) ≠ DTIME(n^k) ?
In "On determinism versus nondeterminism and related problems" (Proc. IEEE FOCS, pages 429–438, 1983), Paul, Pippenger, Szemerédi and Trotter proved that
$\mathsf{NTIME}(n)\neq\mathsf{DTIME}(n)$.
...
- 4,420
1
vote
3
answers
5k
views
Is it possible to have a 4-coloring for a non-planar graph ? [closed]
I have been working on this thread Grid $k$-coloring without monochromatic rectangles, and I am aware that the four color theorem implies that all planar graphs are four colorable.
The question is ...
15
votes
1
answer
943
views
Integer relation detection for Subset Sum or NPP?
Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...
- 2,776
7
votes
3
answers
5k
views
Polynomial Time Algorithm for Graph Isomorphism Testing [closed]
"Michael I. Trofimov" claims that he has found a poly-time algorithm for graph isomorphism, which works for all graphs.
The paper is given in arXiv. The companion website gives a proof-of-concept ...
- 16.3k
11
votes
1
answer
705
views
Time complexity analysis for Reingold's UST-CONN algorithm
What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?
user887
49
votes
9
answers
11k
views
Best Upper Bounds on SAT
In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."
I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time ...
- 16.3k
7
votes
4
answers
903
views
A relaxed Steiner Tree Problem
Given a weighted graph $G(V,E,w)$ where $w$ is the weight function on edges and a subset of vertices $S\subseteq Q$ called terminals, a Steiner Tree is a connected subgraph which connects all vertices ...
- 73
5
votes
1
answer
440
views
Comparing $\mathbf{NP}$ and $\mathbf{E}$
We know that $\mathbf{NP} = \mathbf{NTIME}(n^{O(1)})$ and $\mathbf{E} = \mathbf{DTIME}(2^{O(n)})$.
The complexity zoo states that $\mathbf{E}$ does not equal $\mathbf{NP}$, and cites the following ...
- 16.3k
22
votes
4
answers
4k
views
Where do most REGEX implementations fall on the complexity scale?
Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do ...
- 323
17
votes
2
answers
993
views
Lower bounds on #SAT?
The problem #SAT is the canonical #P-complete problem. It's a function problem rather than a decision problem. It asks, given a boolean formula $F$ in propositional logic, how many satisfying ...
- 6,695
14
votes
4
answers
2k
views
Subrange of a Red and Black Tree
While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual ...
- 242
7
votes
3
answers
859
views
What does it mean that there are differing views on how computations are represented on the Turing Machine?
For a given algorithm (eg reverse the items in this list) and a given type of Turing machine (eg the 3-state 2-symbol busy beaver reduced to 5-tuples) - is there a single simplest way that this ...
- 2,541
36
votes
2
answers
5k
views
Status of Impagliazzo's Worlds?
In 1995, Russell Impagliazzo proposed five complexity worlds:
1- Algorithmica: $P=NP$ with all the amazing consequences.
2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) ...
- 20.7k
13
votes
1
answer
434
views
Efficient algorithm for near-optimal edge-colourings of hypergraphs
Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.
Question.
What efficient algorithms are ...
- 8,871