Most Popular
1500 questions
23
votes
10 answers
Problems that are easy on unweighted graphs, but hard for weighted graphs
Many algorithmic graph problems can be solved in polynomial time both on unweighted and weighted graphs. Some examples are shortest path, min spanning tree, longest path (in directed acyclic graphs), max flow, min cut, max matching, optimum…
Andras Farago
- 11,396
- 37
- 70
23
votes
8 answers
NP-hard problems on paths
everybody knows there exist many decision problems which are NP-hard on general graphs, but I'm interested in problems that are even NP-hard when the underlying graph is a path. So, can you help me to collect such problems?
I've already found a…
Benjamin
- 355
- 2
- 7
23
votes
4 answers
What are the compelling reasons for believing $L\neq P$?
What are the compelling reasons for believing $L\neq P$? L is the class of log-space algorithms with pointers to the input.
Suppose L=P for the moment. What would a log-space algorithm for a P-complete problem look like in its general outlines?
Jumer
- 239
- 1
- 3
23
votes
1 answer
What is the difference between arrows and exponential objects in a cartesian closed category?
In a Cartesian Closed Category (CCC), there exist the so-called exponential objects, written $B^A$. When a CCC is considered as a model of the simply-typed $\lambda$-calculus, an exponential object like $B^A$ characterizes the function space from…
day
- 2,795
- 1
- 20
- 27
23
votes
9 answers
What is the recommended software for drawing data structures such as graphs and trees?
When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?
Chris
- 333
- 1
- 2
- 5
23
votes
6 answers
Is it possible to test if a computable number is rational or integer?
Is it possible to algorithmically test if a computable number is rational or integer?
In other words, would it be possible for a library that implements computable numbers to provide the functions isInteger or isRational?
I am guessing that it is…
dbarbosa
- 365
- 2
- 6
23
votes
5 answers
Good seating arrangements for sequence of meals and tables of size k for a group of people
Given a set $S$ of people I'd like to sit them for a sequence of meals at tables of size $k$. (Of course, there are enough tables to sit all $|S|$ for each meal.) I'd like to arrange this such that nobody shares a table with the same person twice.…
Christian Lindig
- 333
- 1
- 8
23
votes
1 answer
How are Futures described in terms of category theory?
Is there a useful description of futures or promises in terms of category theory? In particular, what could the categorical dual of Future be?
Alexey Romanov
- 551
- 2
- 8
23
votes
1 answer
Cliquewidth of Almost Cographs
(I posted this question to MathOverflow two weeks ago, but so far without a rigorous answer)
I have a question about graph width measures of undirected simple graphs. It is well-known that cographs (graphs which can be built by the operations of…
Bart Jansen
- 5,265
- 21
- 39
23
votes
2 answers
To what extent can an algorithm predict the time complexity an arbitrary input program?
The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs.
I can, however, certainly write a program that can compute the running time of a program of …
Hooked
- 365
- 2
- 12
23
votes
2 answers
Circuit lower bounds and kolmogorov complexity
Consider the following reasoning:
Let $K(x)$ denote the Kolmogorov complexity of the string $x$.
Chaitin's incompleteness theorem says that
for any consistent and sufficiently strong formal system $S$, there
exists a constant $T$ (depending only…
Magnus Find
- 845
- 5
- 14
23
votes
2 answers
Problem in BPP but not known to be in RP or co-RP
Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
arnab
- 7,000
- 1
- 38
- 55
23
votes
3 answers
Clique problem on fixed graphs
As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this case correspond to edges of $K_n$.
It is known…
Stasys
- 6,765
- 29
- 54
23
votes
3 answers
What is known about solutions to sparse integer linear programming problems?
If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what is known about the solution space? I am less…
Dave Doty
- 681
- 6
- 13
23
votes
2 answers
computing the minimal NFA for a DFA
Many years ago I heard that computing the minimal NFA (nondeterministic finite automaton) from a DFA (deterministic) was an open question, as opposed to the vice versa direction which has been known for decades and is well researched with an…
vzn
- 11,014
- 2
- 31
- 64