Is there a notion of computability on sets other than the natural numbers? Is there a notion of computability on sets other than the natural numbers?  For the sake of argument, let's say on sets $S$ that biject with $\mathbb{N}$.
It's tempting to say "yes, they are those functions of the form $g \circ f \circ g^{-1}$ where $g$ is any bijection $\mathbb{N} \to S$ and $f$ is any computable function $\mathbb{N} \to \mathbb{N}$".  I'm cautious of this definition for two reasons.

It privileges $\mathbb{N}$ over other countable sets.  Why is $\mathbb{N}$ special when it comes to defining computability?  I'd like a "coordinate free" definition of computability without reference to any privileged set in the same way I might like a "coordinate free" definition of a linear algebra concept without reference to any privileged basis.

It raises questions about the choice of $g$.  I suspect it may be possible to find contradictions by particularly pathological choices of $S$ and $g$.  For example if I choose $S = \mathbb{N}$ and $g$ some non-computable bijection is it really the case that $g \circ f \circ g^{-1}$ is computable for all computable $f$?
It's tempting to require in the definition that $g$ be computable but unfortunately that's begging the question.

Is there some general way of describing computability on countable sets other than $\mathbb{N}$?

This question is not research-level, but since it is receiving answers, I would like to offer an answer that may actually clear things up a bit, and provide references.

There is an entire area of theoretical computer science which studies computability in analysis, algebra and topology. Of central importance is the notion of computability for real numbers. In fact Turing's original paper on Turing machines starts with the following sentence:

  The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means.

Sometimes it pays to go back to the source.

There are several ways to set up computability on general sets, of which one of the most general ones is realizability theory. The idea of realizability theory goes back to Kleene's paper On the Interpretation of Intuitionistic Number Theory from 1945, but has since been generalized and developed into a mini-branch of computability, with a good mix of category theory, see for instance Jaap van Oosten's book "Realizability: an introduction to its categorical side" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Let me describe the idea of realizability very briefly, and discuss your "coordinate free" requirement later. Start with a model of computation, such as Turing machines, the $\lambda$-calculus, a programming language, or any other partial combinatory algebra (you can even take certain topological spaces to be "models of computation", this stuff is general). For concreteness, let us consider Turing machines. We code Turing machines by natural numbers, but note that I could have taken some other model of computation, so you should not assume that the use of $\mathbb{N}$ is in any way essential here. (Other possibilities include: the powerset of natural numbers, infinite sequences of natural numbers, the syntax of the untyped $\lambda$-calculus, certain categories of games, etc.)

A computability structure on a set $X$ is given by a relation $\Vdash_X$ between $\mathbb{N}$ and $X$, called the realizability relation, such that for every $x \in X$ there $n \in \mathbb{N}$ such that $n \Vdash_X x$. We call such structures assemblies. This definition directly corresponds to the intuitive idea that some piece of data $n$ respresents, or realizes, an element $x \in X$. (For instance, certain sequences of bits represent finite lists of pairs of strings of characters.)

Given two assemblies $(X, {\Vdash_X})$ and $(Y, {\Vdash_Y})$, a map $f : X \to Y$ is realized (or "computable") if there is a Turing machine $T$, such that, whenever $n \Vdash_X x$ then $T(n)$ terminates and $T(n) \Vdash_Y f(x)$. Again, this is a direct transliteration of what it means informally to "program" an abstract function $f$: the corresponding Turing machine does to representing data whatever $f$ does to the corresponding elements.

Assemblies may be extended to a realizability topos. A topos is a model of higher-order intuitionistic mathematics. This tells us that every realizability topos (there is one for each model of computation) contains lots of interesting objects. For instance, it contains an object of real numbers, which thus gives us computability on reals. But it also contains many other objects, such as Hilbert spaces, Banach spaces, spaces of smooth maps, etc. You asked for some other computable structure, but you got something much better: entire mathematical worlds of computability.

Since category theory and toposes can be scary and require some amount of technical proficiency in computability theory, category theory, and logic, we could also work in just one concrete topos, but we express everything in concrete non-abstract ways. A particularly good world of computation arises from Kleene's function realizability, and goes under the name of computable analysis.

Let me comment on the "coordinate free" requirement:

Switching between models of computation gives different kinds of computable worlds. This is a bit like switching between different fields giving different kinds of linear algebra.
A set $X$ may be equipped with many computability structures $\Vdash_X$, just like a set of vectors has many bases. However, while all bases are equivalent, not all computability structures on $X$ are computably equivalent.
If we work concretely with computability structures $(X, {\Vdash_X})$, that is a bit like working with matrices in linear algebra. It can be very useful, but is not abstract.
To work in a "coordinate-free" fashion, we work in a realizability topos and harness the power of category theory (yes, it's a cliché but it works).
We can even work in a "world-free" fashion: develop mathematics in intuitionistic logic, and then interpret the results in realizability toposes.

This is similar to how we define computability in terms of Turing machines and then promptly forget about Turing machines.  Since it turns out a Turing machine is as good a definition as any other, we use it as an anchor for an entire equivalence class of models, and we end up with the same class no matter which element we generate it from. Basically this is the Church-Turing thesis and it defines the set of computable bit strings.

Similarly, to define computability on a different set $S$, we anchor it with a particular partial function from bit strings to $S$.  Actually it does not matter if this function is a bijection or an injection or any other type of function (for a case where we don't really want it to be an injection, consider a group defined by its presentation where we don't have a unique representation for its elements).  It doesn't even have to be a surjection if we permit that singleton sets can be uncomputable. By composing this function with any computable bijection from bit strings to bit strings (a concept already defined), we get a definition of computability for $S$ that's invariant with respect to the function we originally picked (as long as we picked something reasonable).  That is, a CT thesis for our set $S$.  But if we don't pick a reasonable function, we get a different definition of computability.

This function also serves to define the computability of other functions with domain or range equal to $S$. By changing the range to $S$, keeping the domain as $\{0,1\}^*$, we also get an $O(1)$-invariant definition of Kolmogorov complexity for $S$.  And we can finally say that the function we have chosen is itself computable.

So I think the answer to your question is NO. We have to define computability for each set that we want to talk about, because there are non-equivalent definitions. Aside from a very technical or pedagogical discussion it shouldn't be necessary, since a reasonable person can imagine a reasonable definition independently.

But wait, let $S$ be a countably infinite set, and that's it. What's our reasonable definition of computability for $S$? Knowing that the set of bijections between $S$ and $\{0,1\}^*$ is non-empty doesn't tell us which are reasonable. We're out of luck without more details.

And we may encounter multiple inequivalent but equally-reasonable alternatives.  Suppose every tree has some number of red leaves and some number of green leaves, and that for every $r \in \mathbb{N}$ there exists exactly one tree with $r$ red leaves, and that for every $g \in \mathbb{N}$ there exists exactly one tree with $g$ green leaves. Both bijections are reasonable in the sense that we can count the leaves and distinguish the colors, and we can walk aimlessly around the woods counting leaves on trees until we find the tree with exactly $23$ green leaves, or the one with $23$ red leaves. It's not clear whether to identify a tree using  its red leaf count or its green leaf count because this choice leads to inequivalent definitions of computability for sets of trees.  If we instead make our definition by combining the counts with a computable pairing function bijective from $\mathbb{N}^2$ to $\mathbb{N}$ (having appropriately defined computability on $\mathbb{N}^2$), that also uniquely identifies each tree, but the situation is even worse because this is not a bijection between trees and $\mathbb{N}$, now maybe all computable sets of trees are finite!

So in order to avoid the entire discussion it should be understood not only that there exists a reasonable definition of computability on the set in question, but also that there is exactly one class of reasonable definitions.

I think the situation becomes a lot more interesting if we bring time complexity into the picture. Even when just considering integers, our choices matter more. For example, what if we wanted to represent each number as a sum of four squares? We can find such a representation, starting from a base representation, in expected quadratic time with access to randomness. Or instead, as a list of its prime factors, which may or may not be possible to compute in polynomial time. To the extent that we allow hard representations, we lose precision in time complexity. For example, we can't meaningfully say that some function $F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time if we have a representation of $\mathbb{N}$ that might require more than quadratic time to convert to or from a base representation. I think this perspective reveals that base representation is a somewhat arbitrary standard.  (Standard in the sense that base representation is what anyone has in mind when they say something like "$F:\mathbb{N} \rightarrow \mathbb{N}$ is computable in quadratic time", if the underlying model is one that computes bit strings from bit strings and we're supposed to infer the meaning.)


Best known deterministic time complexity lower bound for a natural problem in NP This answer to Major unsolved problems in theoretical computer science? question states that it is open if a particular problem in NP requires $\Omega(n^2)$ time.

Looking at the comments under answer made me wonder:

  Aside from padding and similar tricks,
  what is the best known time complexity lower bound on a deterministic RAM machine
  (or multiple-tape deterministic Turing machine)
  for an interesting problem in NP (which is stated in a natural way)?

  Is there any natural problem in NP which is known to be unsolvable in quadratic deterministic time on a reasonable machine model?

Essentially, what I am looking for is an example that rules out the following claim:

  any natural NP problem can be solved in $O(n^2)$ time.

Do we know any NP problem similar to those in Karp's 1972 paper or Garey and Johnson 1979 that requires $\Omega(n^2)$ deterministic time?
Or is it possible to the best of our knowledge that all interesting natural NP problems can be solved in $O(n^2)$ deterministic time?

Edit

Clarification to remove any confusion resulting from the mismatch between lower bound and not an upper bound:
I am looking for a problem which we know we cannot solve in $o(n^2)$.
If a problem satisfies the stronger requirement that
$\Omega(n^2)$ or $\omega(n^2)$ time is needed (for all large enough inputs) then better,
but infinitely often will do.

Adachi, Iwata, and Kasai in a 1984 JACM paper show by reduction that the Cat and $k$-Mice game has an $n^{\Omega(k)}$ time lower bound.   The problem is in P for each $k$.   The problem is played on a directed graph.    The moves consist of the cat and then one of the $k$ mice alternating steps.  The mice win if they can land on a designated cheese node before the cat lands on them.   The question is whether the cat has a forced win.   It is actually a complete problem so the lower bound is really based on the diagonalization that gives the time hierarchy.

Grandjean showed that the Pippenger, Paul, Szemeredi, and Trotter time lower bound applies to a SAT encoding, though the result of Santhanam may subsume it.

In addition to the time-space tradeoff lower bounds for SAT mentioned in other comments, there is a body of work on branching program lower bounds which imply time-space tradeoffs for Turing machines.    For problems like FFT, sorting or computing universal hash functions there are quadratic tradeoff lower bounds of Borodin-Cook, Abrahamson, Mansour-Nisan-Tiwari but these are for functions with many outputs.   For decision problems in P, there are time-space tradeoff lower bounds that apply for time bounds that are $O(n \log n)$ but these are weaker than are known for SAT.

This is just reasking the same question of P=NP in the a different way, if you can prove that its unsolvable in quadratic time or find an absolute lower bound, you would be proving P!=NP


A variant of Critical SAT in DP A language $L$ is in the class $DP$ iff there are two languages $L1 \in NP$ and $L2 \in coNP$ such that $L = L1 \cap L2$

A canonical $DP$-complete problem is SAT-UNSAT : given two 3-CNF expressions, $F$ and $G$, is it true that $F$ is satisfiable and $G$ is not?

The Critical SAT problem is also known to be $DP$-complete : Given a 3-CNF expression $F$, is it true that $F$ is unsatisfiable but deleting any clause makes it satisfiable?

I am considering the following variant of the Critical SAT problem : Given a 3-CNF expression $F$, is it true that $F$ is satisfiable but adding any 3-clause (out of $F$ but using the same variables as $F$) makes it unsatisfiable?
But I don't succeed in finding a reduction from SAT-UNSAT or even prove it is $NP$ or $coNP$ hard.

My question: is this variant DP-complete ?

Thank you for your answers.

[I made it into a proper answer b/c somebody gave it -1]

If any clause is allowed to be added, then the language is empty -- clearly to any satisfiable formula $F$ you can add a 3-clause $c$ made up of variables that do not appear in $F$: $F \cup \{ c \}$ will be satisfiable.

If the added clauses must use variables of $F$, then the language is in P.

Justification is as follows:

Take any $F \in L$, i.e. $F \in SAT$ and for any 3-clause $c$ on variables of $F$, $F \cup \{c\} \in UNSAT$. Say $c = l_1 \lor l_2 \lor l_3 \notin F$, where $l_i$ is a literal. Since $F \cup \{ c \}$ is UNSAT, all models of $F$ must have $l_i=0$ (for $i=1,2,3$) - because if some model had e.g. $l_1=1$, then it would satisfy $c$ and so $F \cup \{c\}$. Now, assume that there exists another clause $c'$ that is exactly like $c$, but with one or more literal flipped and such that $c' \notin F$, say $c' = \neg l_1 \lor l_2 \lor l_3$. Then by the same argument all models of $F$ must have $l_1 = 1$. Thus, the necessary condition for $F \in L$ is that for each clause $c \in F$ there are exactly 6 other clauses in $F$ that use the three variables of $c$ -- lets call these 7-clause subsets of $F$ blocks. Note that each block implies a unique satisfying assignment to its variables. When this necessary condition is satisfied, $F$ is either uniquely satisfiable or unsatisfiable. The two cases can be distinguished by testing whether the assignments implied by the blocks of $F$ clash, which can clearly be done in linear time.

May I propose an answer to my own question thanks to your comments : the variant of Critical SAT is in P.

Let us call "Problem 1" the variant of Critical SAT : Given a 3-CNF expression $F$, is it true that  $F$ is satisfiable but adding any clause out of $F$ makes it unsatisfiable?

And "Problem 2" : Given a 3-CNF expression $F$ , is it true that $F$ contains all the clauses it implies  and  has a unique model ?

Given a 3-CNF formula, $F$ .

If $F$ is a yes instance of problem 2, then any clause out of $F$ is not implied by $F$ and then covers the only one possible satisfying assignment for $F$ . Adding such a clause to $F$ makes it unsastifiable. $F$ is consequently a yes instance of problem 1.

If $F$ is a no instance of problem 2, then :
Case 1 : it exists a clause out of $F$ which is implied by $F$ . Then adding this clause to $F$ doesn't change its satisfiability. $F$ is consequently a no instance of problem 1.
Case 2 : $F$ contains all the clauses it implies but is unsatisfiabe. $F$ is consequently a no instance of problem 1.
Case 3 : $F$ contains all the clauses it implies but has at least 2 different models. As Kaveh's comment underlines it, « assume that the models differ on variable p, then adding a clause containing it will not change satisfiability. »  $F$ is consequently a no instance of problem 1.

Then, $F$ is a yes instance of problem 1 iff $F$ is a yes instance of problem 2.

Problem 2 is clearly a P problem (for instance, $F$ is a yes instance of problem 2 iff there are exactly $\binom{n}{3}$ = $\frac{n(n-1)(n-2)}{3}$ clauses out of F with no opposite litterals in any two of them – $n$ is the number of variables). So is Problem 1.


What would a very simple quantum program look like? In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first programs I ever wrote was something like

for i = 1 to 10
  print i
next i

Can anybody give an example of code of comparable simplicity that would utilize quantum photonic chips (or similar hardware), in pseudocode or high level language? I am having difficulty making the conceptual jump from traditional programming to entanglement, etc.

Caveat Emptor: the following is heavily biased on my own research and view on the field of QC.  This does not constitute the general consensus of the field and might even contain some self-promotion.

The problem of showing a 'hello world' of quantum computing is that we're basically still as far from quantum computers as Leibnitz or Babbage were from your current computer.  While we know how they should operate theoretically, there is no standard way of actually building a physical quantum computer. A side-effect of that is that there is no single programming model of quantum computing.  Textbooks such as Nielsen et al. will show you a 'quantum circuit' diagram, but those are far from formal programming languages: they get a little 'hand-waving' on the details such as classical control or dealing with input/output/measurement results.

What has suited me best in my research as a programming language computer scientist, and to get the jist of QC across to other computer scientist, is to use the simplest QC model I've come across that does everything.

The simplest quantum computing program I have seen that contains all essential elements is a small three-instruction program in the simplest quantum programming model I've come across.  I use it as you would a 'hello world' to get the basics across.

Allow me to give quick simplified summary of the The Measurement Calculus by Danos et al.1  that is based on is based on the one-way quantum computer2: a qubit is destroyed when measured, but measuring it affects all other qubits that were entangled with it.  It has some theoretical and practical benefits over the 'circuit-based' quantum computers as realized by the photonic chip, but that is a different discussion.

Consider a quantum computer that has only five instructions: N, E, M, X and Z.  Its "assembly language" is similar to your regular computer, after executing one instruction it goes to the next instruction in the sequence. Each instruction takes a target qubit identifier, we use just a number here, and other arguments.

N 2          # create a new quantum bit and identify it as '2'
E 1 2        # entangle qubits '1' and '2', qubit 1 already exists and is considered input
M 1 0        # measure qubit '1' with an angle of zero  (angle can be anything in [0,2pi]
             # qubit '1' is destroyed and the result is either True or False
             # operations beyond this point can be dependent on the signal of '1'
X 2 1        # if the signal of qubit '1' is True, execute the Pauli-X operation on qubit '2'

The above program thus creates an ancilla, entangles it with the input qubit, measures the input and depending on the measurement outcome performs an operation on the ancilla. The result is that qubit 2 now contains the state of qubit 1 after Hadamard operation.

The above is naturally at such low level that you wouldn't want to hand-code it. The benefit of the measurement calculus is that it introduces 'patterns', some sort of composable macros that allow you to compose larger algorithms as you would with subroutines.  You start off with 1-instruction patterns and grow larger patterns from there.

Instead of an assembler-like instruction sequence, it is also common to write the program down as a graph:

 input                .........
    \--> ( E ) ---> (M:0)     v
(N) ---> (   ) ------------> (X) ---> output

where full arrows are qubit dependencies and the dotted arrow is a 'signal' dependency.

The following is the same Hadamard example expressed in a little programming tool as I would imagine a 'quantum programmer' would use.

edit: (adding relation with 'classical' computers)  Classical computers are still really efficient in what they do best, and so the vision is that quantum computers will be used to off-load certain algorithms, analogous to how current computer offloads graphics to a GPU. As you have seen above, the CPU would control the quantum computer by sending it an instruction stream and read back the measurement results from the boolean 'signals'.  This way you have a strict separation of classical control by the CPU and quantum state and effects on the quantum computer.

For example, I'm going to use my quantum co-processor to calculate a random boolean or cointoss.  Classical computers are deterministic, so its bad at returning a good random number.  Quantum computers are inherently probabilistic though, all I have to do to get a random 0 or 1 is to measure out a equally-balanced qubit.  The communication between the CPU and 'QPU' would look something like this:

 qrand()       N 1; M 1 0;
 ==>  | CPU | ------------> | QPU |  ==> { q1 } ,  []
                 start()
      |     | ------------> |     |  ==> { } , [q1: 0]
                 read(q1)
      |     | ------------> |     |
                  q1: 0
 0    |     | <-----------  |     |
 <==

Where { ... } is the QPU's quantum memory containing qubits and [...] is its classical (signal) memory containing booleans.

Danos et al. The Measurement Calculus. arXiv (2007) vol.
quant-ph
Raussendorf and Briegel. A one-way quantum computer.
Physical Review Letters (2001) vol. 86 (22) pp. 5188-5191

I think the programming a quantum computer it should be seen from a different point of view that the normal object-oriented programming.

QC has the same ability of the brain to think and decide. The ability to think means has the power of data-mining a source of data which would be the possible choice, and decide which to pick from the all possible states.

A software at this point would need to be architectured in a way that the qubits represented source of data that can be data-mined and entangled with other groups of data.

QC should have a data-miner that process data reading, linking different option together differents group of datasource which rapresent informations, reading all possible states and choose which one to go on.

Thats how our brain works. The QC is able to understand and act accordingly to the Quantum Mechanic law, that means you give a problem and QC show you all possible solutions to solve it.

that's how powerful could be QC,
do you agree?

https://www.cs.rutgers.edu/~mlittman/papers/openhouse11.pdf
this is the point to start, then
create a dataminer to build the quantum device with gates etc,
a reader connected to the dataminer, to read and provide feedback.
quantum Datasource component host data and the scope of knowledge where the dataminer act.


Which subproblems of 3SAT are still NP complete? The $\mathsf{NP}$-complete problems satisfy the property that if any of them is in $\mathsf{P}$, then all other $\mathsf{NP}$-complete problems are in $\mathsf{P}$.
The problem $3$-SAT is $\mathsf{NP}$-complete, as much as every $k$-SAT with $k\geq 3$.
(On the other hand, $2$-SAT is known to be in $\mathsf{P}$).

Obviously, the problem $3$-SAT can be seen as a subset of $k$-SAT for $k\geq 3$ and, in general, all of them are a subclass of SAT.

However my question goes in the opposite direction: which are some smaller subclasses of $3$-SAT that are still $\mathsf{NP}$-complete?

I am interested in studying the $\mathsf{P} = \mathsf{NP}$ conjecture by looking just into smaller class of $3$-SAT problems that are still acceptable.

I asked a similar question on cs.stackexchange.com, perhaps Juho's answer can help you; it contains references to: MONOTONE NAE-3SAT, MONOTONE 1-in-3-SAT, PLANAR 3SAT, k-COLOURABLE MONOTONE NAE-3SAT.

You can find other variants also in this cstheory question: 4-BOUNDED PLANAR 3-CONNECTED 3SAT, POSITIVE PLANAR 1-in-3 SAT.

there are many answers to this cited elsewhere, here is one additional one that maybe captures the boundary between P/NP in a natural way and fittingly along the lines requested. a distinctive/ interesting model is the $(2+p)$-SAT model for $0 \leq p \leq 1$ inspired by research relating to phase transitions and statistical mechanics. the idea is that instances have a count of 2-width and 3-width clauses in a mixture wrt the $p$ ratio. two papers:

Rigorous results for random (2 + p)-SAT / Achlioptas, Kirousis, Kranakis, Krizanc
2+ P-SAT: Relation of Typical-Case Complexity to the Nature of the Phase Transition / Monasson, Zecchina, Kirkpatrick, Selman, Troyansky


Grid $k$-coloring without monochromatic rectangles Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known.

Anyone feel up to trying 5-colorings? ;)

The following question arises out of Ramsey Theory.

Consider a $k$-coloring of the $n$-by-$m$ grid graph. A monochromatic rectangle exists whenever four cells with the same color are arranged as the corners of some rectangle. For example, $(0,0), (0,1), (1,1),$ and $(1,0)$ form a monochromatic rectangle if they have the same color. Similarly, $(2,2), (2,6), (3,6),$ and $(3,2)$ form a monochromatic rectangle, if colored with the same color.

Question: Does there exist a $4$-coloring of the $17$-by-$17$ grid graph that does not contain a monochromatic rectangle? If so, provide the explicit coloring.

Some known facts:

$16$-by-$17$ is $4$-colorable without a monochromatic rectangle, but the known coloring scheme does not appear to extend to the $17$-by-$17$ case. (I'm omitting the known $16$-by-$17$ coloring because it would very likely be a red herring for deciding $17$-by-$17$.)
$18$-by-$19$ is NOT $4$-colorable without a monochromatic rectangle.
$17$-by-$18$ and $18$-by-$18$ are also unknown cases; an answer to these would be interesting as well.

Disclaimer: Bill Gasarch has a $289 (USD) bounty on a positive answer to this question; you can reach him through his blog. A note on etiquette: I'll make sure he knows the source of any correct answer (should one arise).

He brought it up again during a rump session at Barriers II, and I find it interesting, so I'm forwarding the question here (without his knowledge; though I highly doubt he would mind).

Some of you are probably aware of this, but the 17 x 17 coloring problem has been solved by Bernd Steinbach and Christian Posthoff.  See Gasarch's blog post here.

This is Bill Bouris. Hi, Dan. I'm working on a program that searches for a suitable 17x17 matrix which exhibits no-4-coloring according to Ramsey's Theory. I use a positional matrix depicting all connections between points and fix the main diagonal and allow the top row of the matrix to run through all of the possible 16choose8 combinations; I capture only the matrices that pass regarding the following criteria... no-XRRR, no-RXRR, no-RRXR, no-RRRX, no-XBBB, no-BXBB, etc., then I sweep through the matrix using the next weakest criteria... no-XBRR, noBXRR, no-BBXR, no-BBRX, no-XRBB, no-RXBB, etc. for a total of 32 sweeps until the computer fills in the coloring automatically. I've noticed that there's a possible candidate per every 400 matrices out of a total 12780, and it takes .95 hours to find the candidate or 1 per every 8.644 seconds. It's coming along, but I don't have much time to program it... as I work full-time. We should work together... I could use the $289.00!


Finding cliques in a big graph I would like to find (all) cliques in a given graph with 8,568 vertices and 12,726,708 edges. The vertex with the lowes degree has 2000, the vertext with the highest degree has 4007.
The cliques should have exactly 17 vertices.

The algorithm should be fast, because of the size of the graph.

I had the following idea:

Delete all vertices with a degree of 16 or less.
Iterate over every vertex

try to add another vertex:

If the clique has exactly 17 vertices: Add it to a list
Else: Keep trying to add vertices

If no more vertices can be added: go back to the latest point where you had the choice to add some vertices and add one of those that could not be added before.

I didn't implement this algorithm, because I think it will be quite slow. Do you know better ones?

These kind of problems are in general very hard with the decission version of a problem often being NP-hard, so I doubt you will find an algorithm fast enough, unless your graph has some peculiarity which allows you to discard a large number of vertices.

Since you restrict it to cliques of exactly 17 vertices then trivially there is an $O(n^{17})$ algorithm, but I'd hardly call this fast. To do this simply step through all subsets of 17 vertices in lexicographical order and check whether they form a clique. Note that this is exactly $\binom{n}{17}$ subsets. Note however, that for an input graph which is itself a clique, there are $\binom{n}{17}$ cliques of comprised of 17 vertices, and hence this trivial algorithm is optimal if we consider only worst case scaling, since simply reading a list of all such cliques takes $\binom{n}{17}$ steps. In order to do better than this, you need a graph with some structure.

So for your specific case of $n=8568$ you potentially have $2 \times 10^{52}$ cliques of 17 vertices. Further since you have more than 12 million edges, this is enough for a maximally connected graph of 5000 vertices, which would have approximately $2 \times 10^{48}$ unique subsets 17 vertices which form cliques, so for the parameters you have listed it is entirely possible that you simply cannot enumerate cliques fast enough to give you a reasonable run time.

I'm not seeing why the CLRS (p. 617) version of Strongly-Connected-Components() doesn't solve your problem. And it's just 2 DFS's to find all cliques of any size. So, when you're done, you just restrict the result set to those cliques with 17 vertices. That's just O(n + k) because DFS is the limiting factor.
The structure of your graph might also make your idea of deleting vertices of degree 16 a nice way to speed things up.
2 DFS's on 12.8M edges certainly is likely not going to be blazingly fast, but I would think it would be doable in a reasonable amount of time. I'm unfortunately not seeing how you could multi-thread it.
I've got some Java code that does a DFS and stronglyConnectedComponents() if you think it might be of use to you (my email: info@marshallfarrier.com; and please do email me if you're interested, as I'd be interested to see how my code works on something that big!).
Or am I misunderstanding the problem altogether? (if so, my apologies)


Algorithm to compute distance between powers Given coprime $a, b$, can you quickly compute $$ \min_{x, y > 0} |a^x - b^y| $$

Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these powers get? Also, how do we quickly compute the minimizing $x, y$?

First I thought it would be best to use the continued fraction of $\log(a)/\log(b)$ and test at its convergents, because at that convergents there are points $(x,y)$ of in some sense optimal approximation. After that it becomes clear, that one needs to use at least the generalized continued fractions to make sure to have monotonic decreasing distances.
After that and the complicated algorithm with this the following brute-force algo was even faster in Pari/GP

\\ print X,Y,d conditional X>lowboundX, Y > lowboundY, d<upperboundD
{pri1(lbX,lbY,ubd,a,b,X,Y,d)=if(X<lbX || Y<lbY || abs(d)>ubd,return(0));
                  print(a,"^",X,"-",b,"^",Y,"=",d)); }

{mylist(maxa=19,maxb=99,lbX=3,lbY=2,ubd=100)=print(" ");
for(a=2,maxa,for(b=a+1,maxb,
     if(gcd(a,b)>1,next()); \\ ignore trivial multiples
     X=1;Y=1;Xa=a;Yb=b;
     d=Xa-Yb;  pri1(lbX,lbY,ubd,a,b,X,Y,d);
     for(k=1,20,
        while(d<0,Xa*=a;d=Xa-Yb;X++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        while(d>0,Nb*=b;d=Xa-Yb;Y++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        if(X>30 || Y>20, break());  \\ stop at max X=30 or Y=20
       );
   )); }

after that call mylist(100,1000,3,3,100) to find all small difference with $|d| \lt 100$ where both exponents are at least $3$ for all bases $a=2..100$ and $b=(a+1) .. 1000$ . Check only up to $\max (X)=30$ and $\max(y)=20$.

This was much faster than the continued-fraction approach (which also had more unkind issues (for instance with completeness of the solutions) which are difficult to handle) although it is a somehow naive algo ...

A protocol (manually ordered) :

gettime();mylist(200,10 000,3,3,100);gettime() /1000.0 \\ ~ a*b/6000 sec
  (400 sec)

 2^8- 3^5= 13

 6^7-23^4= 95
 2^7- 3^4= 47

 2^7- 5^3=  3
 2^5- 3^3=  5
 3^4- 4^3= 17

---------------
 2^6- 3^4=-17

 3^5- 4^4=-13
 2^5- 3^4=-49

 2^8- 7^3=-87
(4^4- 7^3=-87)

 3^7-13^3=-10
 2^6- 5^3=-61
(4^3- 5^3=-61)
 2^5- 5^3=-93

 2^4- 3^3=-11
 3^4- 5^3=-44
 6^4-11^3=-35
15^4-37^3=-28

 3^3- 4^3=-37
 3^3- 5^3=-98
 5^3- 6^3=-91


Quality of a conference I am a physicist working in TCS in a new group. I would like to know, given a conference (imagine your favorite ones),  how can I know the quality of this conference and also the quality of the journal where the proceedings will be pusblished (in case they are). I heard something about CORE classification but found no link or more information about. Thanks

P.S.: I find TCS stack exchange very interesting for TCS discussions (obviously). I just wonder if there is any similar stack exchange academic site for physics/chemistry. I found physics.stackexchange, but some questions related with journals were instantly classified as offtopic

Usually, you should be able to figure out who are the leading researchers or research groups in your research area.

Everything else is then usually fairly straightforward: just find out in which conferences the leading researchers publish their work, and in which conferences they serve in programme committees, etc. Most likely those would be the most relevant conferences for your work as well.

The same applies to journals as well.

(Note that the most relevant conference is not necessarily the same as the most prestigious conference, but it might be a good idea to start with relevant conferences... Your work might have much more impact that way, even if it does not look that impressive in your CV.)

I recommend Microsoft Academic Search.  See for example: a ranking list for TCS conferences


Is there a theory to answer "the simplest program to solve a problem"? To answer "what problems can be solved by computing", we developed the theory of computability. For the problems that are computable, is there a theory to answer the question "is the program I get the simplest one"?

I do not think computational complexity answer the question. I think it considers how long we need (though measured abstractly).

I am not sure whether algorithmic information theory answer the question. It seems that the theory talks about size, where the equivalence of minimal size and simplest is not obvious to me (well, at least they feel different to me).

I think the theory should at least define "simple" or "simpler than" relation.

I am now convinced that I should look into Kolmogorov Complexity. However, I would like to explain what was in my mind when I was asking the question.

When I improve a program, I try to reduce unnecessary connections between different parts of the program (maybe re-dividing parts so that there can be less or weaker connections). Since the connections are reduced, the program feels "simpler". Hence the choice of the word "simple" when I am phrasing the question. It is very likely the size of the program also decreases, but that is a good side effect, not the main goal. Obviousely, the improving process cannot go forever. There is a point that I should stop. If, only by considering the "structure" (sorry for another undefined concept) or "relation", can I convince myself that nothing more can be done?

Here contains better description of my notion of complexity.

Olaf Sporns (2007) Complexity. Scholarpedia, 2(10):1623

This problem is studied in Algorithmic Information Theory. What you're defining is called Kolmogorov-Chaitin complexity.

http://en.wikipedia.org/wiki/Kolmogorov_complexity

And it seems that the notion of simplicity that you're requiring can be formalized via the notion of complexity measure, which is formalized by Blum's axioms.

http://en.wikipedia.org/wiki/Blum_axioms

It seems also that it is possible to generalise Kolmogorov's complexity to take
other complexity measures into consideration. See reference below. (Wikipedia's article on Kolmogorov complexity addresses this issue.)

Burgin1990- Generalized kolmogorov complexity and other dual complexity measures
Cybernetics and Systems Analysis Volume 26, Number 4, 481-490

There are different kind of approach to decide what is a simple code and what is not.

But sadly, there are not a automatic way to determine it, for example, Kolmogorov Complexity fail with recursive functions, some recursive functions (logical deep) are simple but the understanding about it is not so simple.

In my experience, our team was working in a system and we found a "simple" procedure in Oracle (no more than 50 lines)... and we tried to understand it, it took 2 months (and several meetings) for fully understand it, not by the complexity of the code but in the logic behind every variable.

I think the way to determine how simple is a code is :"read a code and consider the time used to understand it."

So "The simplest program to solve a problem?" can be divided in:

a) simplicity of the code (clear code) but it is too subjective.

b) overcomplexity of the function, if i have X problem then i must solve DX (Delta X) task to solve it, where DX must trend to X.

For example, if my problem is (one) "to peel an apple" and i must do it in PHP (and language) then

if i am extremely lucky and PHP have the function function_peel_apple() then it is the simplest code ever X=1 DX=1, just call the function and that's it!.

In opposite, if i am not so lucky but exist the function function_peel() and function_get_apple() then X=1 (one problem) and DX=2 (two task).

If, in the worst case, does not exist any function, then i must create one (or more than one) by myself and it add several task prior to solve the problem, now that's is a complex program.


Regular Graphs and Isomorphism I would like to ask whether there is an already published result on that:

We take all possible different paths between each pair of nodes of two connected regular (with degree $d$ let's say, and number of nodes $n$) graphs and write down their lengths. Of course this number of distinct paths is exponential. My  question is, if we sort the lengths and compare them (the lists obtained by the two graphs) and they are exactly the same, can we say that the two graphs are isomorphic?

Of course, even if this is a result we cannot use it to reply for Graph Isomorphism, since the number of distinct paths is exponential, as said

By distinct paths, I refer to paths having at least one different node, obviously.

Thanks in priori for your help.

I believe the answer to your question is "no" because an equivalent condition would imply a polynomial time solution to GI.

For $A$, the adjacency matrix of the graph $G$, note that the number of paths from $i$ to $j$ of length $k$ is $(A^k)_{i, j}$ (with repetition of vertices and edges allowed).  For two graphs $G_1$ and $G_2$ (with adjacency matrices $A_1$ and $A_2$) and $k \ge 1$, if you sorted the elements of $A_1^k$ and $A_2^k$ then in order for $G_1$ to be isomorphic to $G_2$, it is a necessary condition that the lists be identical for all $k$.

I believe your conjecture is equivalent to:

If the sorted lists of elements of $A_1^k$ and $A_2^d$ are identical for $k = 1$ to $n - 1$ (upperbound on the longest path with non-repeating vertices) then $G_1$ and $G_2$ are isomorphic.

So to solve GI, one only has to perform $n - 1$ multiplications of $n \times n$ matrices (and a little extra time to sort and compare $n^2$ elements).  This would take less than $n^4$ time.

I admit two possible flaws in my argument.  First, it is totally possible that GI has a polynomial time algorithm and that we just discovered it together, just now (hooray, we're famous!).  I find this highly unlikely.  Second (and much more probable), what I've proposed is not actually equivalent to your conjecture.

Final thought.  Have you tried this out for all, say, 3-regular graphs for size 8 or so?  I would think that if your conjecture is false, that there should be a counter example in 3-regular graphs of fairly small size.


Is a turing machine with random number generator more powerful? Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a classical TM do, but what about the converse?

One can argue that the classical TM will always generate the same result given the same input,  while the TM with randomness can behave randomly, it can do more. But, then random-valued functions are not really what we call computable. I am aware of randomized algorithms and BPP and what not, but is there an extension of computability that deals with these kind of questions?

seems like an active, even central/core area of current research under the heading of "exact power of derandomization". its basically an open question with various open complexity class separations whether randomization adds power, or doesnt. theres also a deep connection to the $\mathsf{P \stackrel{?}{=}NP}$ problem in the natural proofs result of razborov/rudich which shows that, loosely, a $\mathsf{P \neq NP}$ proof would likely allow one to "break" what are now conjectured as "secure" random number generators.

[1] is a broad survey on derandomization literature by Impagliazzo. (think there are other surveys out there but cant find them this moment.) [2] is a rough outline of natural proofs paper. there is also a lot of connection of randomization (via pseudorandom generators) across the semifamous "5 algorithmic worlds" introduced also by Impagliazzo.[3]

basically various complex algorithms have been successfully derandomized in significant advances, but others resist efforts. one famous case study would be the AKS primality algorithm which for decades was a probabilistic test that was cleverly derandomized by AKS & proven to run in P time.

[1] Can every randomized algorithm be derandomized? by Impagliazzo 2006

[2] Natural proofs explained by chris calabro

[3] 2009 workshop on impagliazzos 5 worlds


Is it possible to represent a regular expression with bounded captures using a DFA and O(1) additional processing? It's well known that a regular expression can be converted to a non-deterministic finite state automaton, which can in turn be converted in to a deterministic finite state automaton. These DFAs can then be compiled directly into code as in e.g. re2c.

However, most libraries for regular expressions allow for captures - where the portion of the string representing a certain portion of the regex is saved for further analysis. With captures things get more complex - a state node passed in an early match may not be able to commit to a capture, as whether the capture is correct or not depends on later nodes.

Although a turing machine can obviously handle such expressions by treating the regex as a NDFA, and maintaining a stack of non-deterministic state transitions (ie backtracking), it's desirable to avoid the unbounded additional memory/CPU usage and allocations this entails.

So: Is it possible to compile a regular expression with a bounded number of captures $(< k)$ into a DFA, allowing $O(1)$ additional processing at each node, and $O(k)$ additional storage?
If not, is there a proof to this effect?

I have no direct answer, but some additional remarks regarding on the topicality of my paper from this year's STACS which Raphael  mentioned in his answer. (Due to space reasons, I opted for a new answer, instead of a comment.)

As far as I understand the question, the classes of regular expressions with $\leq k$ captures corresponded to the classes RegEx(k) of extended regular expressions with at most $k$ variables in my paper. Among the results in the paper, the ones that are probably most relevant to the question are that, even with one variable (the class RegEx(1)),

1) there is no effective way of converting expressions from RegEx(1) to "proper" regular expressions, even if the problem is restricted to those expressions that describe regular languages,

2) even if one is able to convert these expressions with one variable to proper regular expressions (or any other description mechanism for the class of regular languages), the resulting blowup in size is not bounded by any computable function,

3) given an expression $\alpha\in RegEx(1)$, universality (the question whether $L(\alpha)=\Sigma^*$) is not decidable.

This does not directly answer the question, but imposes some limits on possible conversion procedures. For example, if the universality problem for the class of resulting DFAs with extra storage is decidable, such a conversion procedure cannot exist. (On the other hand, although the automata model that is described in the question appears to be underspecified regarding the storage and storage operations, I am under the impression that this problem should be undecidable for the resulting class of automata.)

Among the few papers that deal with regular expressions with variables/backreferences/captures, I know of only two other works that consider something in the direction of limiting the number of variables: Aho's chapter on string matching in the Handbook of TCS (Vol. A), which contains a sketch of a proof that extended regular expressions with at most $k$ backreferences can be matched in time $O(n^{2k})$, and the paper by Reidenbach and Schmid from CIAA 2010, which gives a polynomial time matching algorithm for a larger class of extended regular expressions.

Implementation of backreferences in regular expressions is equivalent to 3SAT, and therefore NP-complete.

However, simple submatch extraction is possible using only a DFA, even though the majority of implementations do not.


Calculating the instantaneous period of a wave I have a set of data which represents slightly imperfect waves of varying amplitudes and periods. I wish to calculate the instantaneous period of the wave around any point within this data set - simply finding the local minima and maxima representing each individual wave and calculating the frequency of these is not precise enough for my needs.

Is there a known algorithm that can achieve this? Even better, an existing implementation of this algorithm? I am currently programming in R, but am willing to switch if needed.

n.b. if this is the wrong StackExchange site for this question, please direct me to a better one.

The instantaneous frequency of a wave is defined as $f(t) = \frac{1}{2\pi}\frac{d\phi}{dt}$ where $\phi$ is the instantaneous phase. See the Wikipedia page on Instantaneous Frequency.

Presumably you have discrete data, in which case you need to estimate $\phi$ and its derivative numerically.

This isn't an entirely meaningful measure, since it doesn't make very much sense to ascribe a frequency to a non-periodic function, but nonetheless there does seem to be a convention for it.

Let me close by saying that I don't consider this a TCS problem. It is firmly in signal processing territory, and so I wouldn't consider here the ideal venue for such questions.

There is no such thing as the instantaneous period of a wave.  The Heisenberg uncertainty principle guarantees this.  Oh you can find a set of estimated frequencies for a given window over the signal, but that is frequencies for the whole window, not for that instant.   You need to figure out what size of time-frequency window satisfies your needs and then calculate something the Fourier transform for that window over the entire signal (and maybe search the resulting frequencies for the peak).

Two things to remember, the larger the window, the higher the frequency resolution (how many frequencies you can see), but the smaller the time resolution (when something happened--and this is a bit hard to explain as it's been a few years since I've had to learn and deal with it extensively so I may not be saying it right).

Another factor is that amplitude (multiplication in the time domain) is convolution in the frequency domain.  To remove some artifacts of that you may have to do some filtering (that is, convolution in the time domain or multiplication in the frequency domain.)  It might even make sense to filter with one widow size then do analysis with another window size.  There's a lot of finicky business when it comes down to signal sampling.

Edit:

Ok, this "Heisenberg uncertainty principle" with regard to signal sampling is not some random thing I pulled out of my ear one day.  It is, AFAIK, a well established concept within Wavelet literature.  (Wavelets involve a whole family of mathematical non-Fourier techniques to analyze a signal)  "The World According to Wavelets: The Story of a Mathematical Technique in the Making" by Barbra Burke Hubbard (ISBN 1-56881-072-5) devotes at least one (if not two) chapters to the subject and has a proof in the Appendices.

According to her, (I'm going to have to paraphrase as my attempts to translate to Mathjax/TeX/LaTeX are failing, please also forgive as it's been years since I've looked at this anyway)  For every $f(t)$ ($t$ a real number) such that the integral (from negative infinity to positive infinity) of $|f(t)|^2$ with respect to $t$  equals $1$, the product of the variance of $t$ and the variance of $\tau$ (the variable of $\hat f$) is at least $1/(16*\pi^2)$, and then gives a large, explicit inequality to state what exactly she means with further non mathematical explanation throughout the chapter.

I will make no attempt to explain further, partially for fear I'd likely mess up. But if you want, you can read that and/or its references and see that, yes, the Heisenberg uncertainty principle does indeed apply here.


Current parallel models for computation The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s.

Are these areas still active in terms of research for parallel algorithms? Are there newer more sophisticated models for parallel computation? Are general models still in vogue, or are researchers trying to specialize with GPGPU or Cloud based computation coming in fashion?

I apologize beforehand for the blog-post format of my answer. I couldn't help myself making a small overview of the parallel computing world.

You can categorize parallel programming models in roughly two categories: control-flow and data-flow models.

The control-flow models try to make parallelism work within the context of a explicit-control program, basically every programmable computer today.  The fundamental problem being tackled is that such a 'Von Neumann architecture' was not designed for parallel execution, but efficient sequential computations.  Parallelism in such context is obtained by duplicating parts of the basic modules (memory, control, arithmetic).

Duplicating only arithmetic gives you SIMD instructions, all ALUs share the same Program Counter (PC) and thus always execute the same operation in parallel, albeit on different data.

Duplicating ALU and the PC but keeping the instruction sequencer inside the control unit gives you Out of Order (OoO) execution that yield some pipeline-parallelism. In this category you also have the Very Long Instruction Word (VLWI) and branche-prediction techniques. You rarely see this category at a software level though.

Going a bit further is duplicating the whole 'core' but keeping the memory shared, these are the current multicore processors that give you task (or thread) parallelism.  Sharing memory in this context gives you very, very hard and subtle concurrency issues.  Parallel computations on current multicore are thus completely revolving around synchronization/concurrency problems, the careful balance of performance (no sync) and desired semantics (totally synchronized, sequential execution semantics). Examples of this is the PRAM or more popular these days the Cilk ofshoots such as fork/join (IntelTBB, Java.Utils.Concurrency). CSP and Actor models are concurrency models, but as mentioned above concurrency and parallelism become blurred in a shared-memory environment. n.b. parallelism is for performance, concurrency to maintain correct semantics.

Duplicating memory too gives you either networked computers that get programmed with MPI and its ilk or just strange non-Von Neumann architectures such as the network-on-a-chip processors (cloud processor, the Transputer, Tilera). Memory models such as UMA or NUMA try to maintain the illusion of shared memory and can exist on either software or hardware level. MPI maintains the program-level parallelism and only communicates via message passing. Message passing is also used on a hardware level for communication and concurrency (Transputer).

The second category are data-flow models. These were designed at the dawn of the computer age as a way to write down and execute parallel computations, avoiding the Von Neumann design.  These have fallen out of vogue (for parallel computing) by the '80s after sequential performance rose exponentially. However, a lot of parallel programming systems such as Google MapReduce, Microsoft's Dryad or Intel's Concurrent Collections are in fact dataflow computational models.  At some point they represent computations as a graph and use that to guide execution.

By specifying parts of the models you get different categories and semantics for the dataflow model. What do you restrict the shape of the graph to: DAG (CnC, Dryad), tree (mapreduce), digraph?  Are there strict synchronization semantics (Lustre, reactive programming]? Do you disallow recursion to be able to have a static schedule (StreaMIT) or do you provide more expressive power by having a dynamic scheduler (Intel CnC)? Is there a limit on the number of incoming or outgoing edges? Do the firing semantics allow firing the node when a subset of the incoming data is available? Are edges streams of data (stream processing) or single data tokens (static/dynamic single assignment). For related work you could start by looking at the dataflow research work of people like Arvind, K. Kavi, j. Sharp, W. Ackerman, R. Jagannathan, etc.

Edit: For the sake of completeness. I should point out there are also parallel reduction-driven and pattern-driven models. For the reduction strategies you broadly have graph-reduction and string-reduction. Haskell basically uses graph-reduction, which is a very efficient strategy on a sequential shared-memory system. String-reduction duplicates work, but has a private-memory property that makes it better suited to being implicitly parallelized. The pattern-driven models are the parallel logic languages, such as concurrent prolog. The Actor model is also a pattern-driven model, but with private memory characteristics.

PS. I use the term 'model' broadly, covering abstract machines for both formal and programming purposes.

this will be considered controversial by some, and even proponents of this angle will have to admit its in the early stages of research, but basically quantum computing seems to have many connections to parallelism and parallel computation. the references are right now scattered but an emerging theme can be seen by a determined researcher.

maybe the best connection is with Grovers search algorithm which has recently been shown to be more general in the sense of being usable for speedup on most NP complete problems in general[5]. Grovers algorithm seems to have a strong analogy/connection with parallel database search algorithms. the best classical serial algorithms cannot meet the same performance but at least one authority recently argues that QM approaches for search actually do not outperform parallelized classical algorithms.[1]

further evidence are schemes that explicitly look at the parallelism in quantum search eg [2]. also quantum simulator(s) have been proposed that are based on parallel/distributed processing[3][4] and because the scheme fits well & leads to efficient and tractable simulations (30 qubits are simulated in ref [3]), this conversion is surely not merely a coincidence and indicates a deeper bridge between parallel classical computing and QM computing, but probably so-far uncovered.

[1] Is quantum search practical? by Viamontes et al

[2] Exact quantum search by parallel unitary discrimination schemes by Wu/Dian

[3] General purpose parallel simulator for quantum computing by Niwa, Matsumoto, Imai.

[4] efficient distributed quantum computing by Beals et al 2012

[5] Solving NP complete problems with quantum search by Furer 2008


Finding a minimum "node" weight path Suppose a graph with node weights only (no edge weights). For a given source-sink pair, how can I find a path with the minimal sum of node weights? Does this problem have a name? Is it possible to reformulate this to a shortest-path problem?

If both nodes and edges are weighted, is it still possible to find a min-weight path?

You can treat this as a directed graph problem, where the weights of all edges coming into a node are equal to that node's weight.

If the edges are weighted too, add the node's weight and the edge's weight together to find the incoming edge's weight in the directed graph.

The question can be posed as a branch-and-bound problem.

Perform a breadth-first search, extending the path with the smallest incremental increase in cumulative weight. Terminate any paths that reach already seen nodes. Continue until you reach the desired destination node.

Given that you have no geometric measure, the search can, in the worst case, result in a crawl of the entire graph. If you any distance measure to the destination from each node, use that to select the next hop to explore.


Complexity of interval cover problem Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to select a minimum number of intervals $[l_i,r_i]$ such that for every $i=1,…,2n$, at least $d_i$ intervals containing the integer $i$ are selected.

It is not hard to see that $Q$ can be solved in polynomial time (see below).

Now consider the following slightly modified problem $Q’$: The input of the problem is the same as before. However, the task now is to select a minimum number of intervals such that for every $i=1,…,n$, at least $d_{2i-1}$ intervals containing the integer $2i-1$ or at least $d_{2i}$ intervals containing the integer $2i$ are selected (with “or” we mean the usual logical or).

My question: Can $Q’$ be solved in polynomial time?

Here are two ways to solve $Q$ efficiently:

A simple greedy algorithm: Sweep through the intervals from left-to-right and select only as few intervals as are necessary to “satisfy” the numbers $d_i$. Whenever there is a choice between different intervals, choose the one(s) with maximal right endpoint.

An integer program: For each interval $[l_i,r_i]$ introduce a decision variable $x_i\in\{0,1\}$ with $x_i=1$ iff the interval is selected. The objective is to minimize $ x_1+…+x_k$, subject to the constraints $\sum_{j:i\in[l_j,r_j]} x_j\geq d_i$. The constraint matrix of this integer program has the consecutive ones property and therefore the linear programming relaxation of this program has an integer optimal solution.

Thanks for any hints, and also for references!

Every instance of Q can be transformed into an instance of the Multiple Set Cover Problem, where the locations are the intervals $[l_i,r_i]$, covering a consecutive sequence of demand points (=integers $d_i$).


SAT algorithms not based on DPLL Are there any algorithms for SAT solving which are not DPLL based?
Or are all algorithms used by SAT solvers are DPLL based?

Resolution Search (just applying the resolution rule with some good heuristics) is another possible strategy for SAT solvers. Theoretically it's exponentially more powerful (i.e. there exist problems for which it has exponential shorter proofs) than DPLL (which just does tree resolution though you can augment it with nogood learning to increase its power - whether that makes it as powerful as general resolution is still open as far as I know) but I don't know of an actual implementation that performs better.

If you don't limit yourself to complete search, then WalkSat is a local search solver which can be used to find satisfiable solutions and outperforms DPLL-based search in many cases. One can't use it to prove unsatisfiability though unless one caches all the assignments that have failed which would mean exponential memory requirements.

Edit: Forgot to add - Cutting planes can also be used (by reducing SAT to an integer program). In particular Gomory cuts suffice to solve any integer program to optimality. Again in the worst case, an exponential number may be needed. I think Arora & Barak's Computational Complexity book has a few more examples of proof systems that one could in theory use for something like SAT solving. Again, I haven't really seen a fast implementation of anything apart from DPLL-based or local search based methods.

DPLL does not strictly specify the variable-visit ordering and there is a lot of interesting research looking at optimal variable ordering attack strategies. some of this is incorporated into variable selection logic in SAT algorithms. in a sense some of this research is preliminary in that it shows that different variable attack orderings lead to different sequential constrainedness (which is highly correlated with instance hardness), and devising the most effective heuristics or strategies to exploit this apparently key insight seems to be in the early stages of research.

Guiding Real-World SAT Solving with Dynamic Hypergraph Separator
Decomposition Li, van Beek
Decomposing satisﬁability problems
or
Using graphs to get a better insight into satisﬁability problems Herwig
The Constrainedness Knife-Edge (1998) Walsh


Difference between PRAM and machine model in dynamic multithreading In the first edition of Introduction to Algorithms (Cormen et al., MIT Press, 1990), the discussion of parallel algorithms is based on the PRAM model. In the second edition, paralellism has been eliminated, but in the third edition (Cormen et al., MIT Press, 2009), the topic is reintroduced, but with a dynamic threading model (based on Cilk). The chapters are very different, for sure, and the models seem to be, as well, at least superficially. But I'm wondering: What are the differences in the underlying computational model or abstract machine here?

Their underlying model is still a shared-memory RAM machine with multiple processors. How is this different from the PRAM? Is it the case, perhaps, that they are in fact using the same underlying model, but approaching it differently? The threading is certainly handled differently in the classic PRAM algorithms – more in line with static threading, where you manually schedule which threads/processes are to run on which processors, rather than simply express concurrency/potential parallelism and have some automatic scheduler use the processors available. But still: Are there more fundamental differences?

In their chapter notes (3rd ed., Chapter 27), Cormen et al. write, “Prior editions of this book included material on […] the PRAM (Parallel Random Access Machine) model.” This seems to indicate that they do not view their dynamic multithreading as being built on this model. Is this so? If so, what differences am I missing?

Dynamic multithreading (like Cilk) does not involve processors working synchronously (in lockstep), for instance. PRAM is (sort of) SIMD, while DM is (sort of) MIMD. Notice that there are async PRAM models, but none seem to have gathered enough pull. Notice also that DM assumes logical parallelism, while PRAM is very much explicit parallelism, and that PREM machines (unlile DM) don't really exist beyond the lab.

Update:

This answer was based on the assumption that DM was a programming model and the fact that PRAM is a computing model, but Dervin pointed out that DM is also a computing model which is correct.


shortest path & max flow I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book.

We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ where weight of every edge $(u,v) \in E$ is a positive number ($w(u,v)>0$).

Actually it asks to prove that finding the shortest path from $s$ to $t$ is equivalent with finding a max flow $f$ from $s$ to $t$.

$f$ minimizes the amount of $Σ_{(u,v)\in E} f(u,v)w(u,v)$ and has the value of $|f|=1$.

It seems that i am missing something. Can anyone help me with this cause i really hate leaving unsolved exercises when reading a book.

Thanks.

What you're describing, where you minimize the sum of $f(u,v)w(u,v)$ with a given flow value $|f|$ isn't, in fact, the max-flow problem—it's the min-cost flow problem. If you constrain the flow value to be 1, and all capacities are set to 1, it's pretty clear that this problem is equivalent to finding the shortest path.

Basically, unit-capacity flow problems find edge-disjoint paths. If you set the flow value to be 1, you'll find only a single path. If you're working with min-cost flow, that path will necessarily be the shortest path (and, therefore, the cheapest flow).

If this is not what the book is asking, and it's really asking you about max-flow, I suspect there must be some details missing from your description. (For example, you could easily have a single node $t'$ before $t$, with $c(t',t)=1$, so max-flow would have a flow value of 1, yielding a single path; however, that would still ignore the edge costs, and would just find any path, unless you're specifically using the Edmonds-Karp algorithm, which uses BFS to find its augmenting paths; in that case, you would, at least, find the shortest unweighted path.)

Actually finding the min-cut from s to t (whose cut has the minimum capacity cut) is equivalent with finding a max flow f from s to t.

There are different ways to find the augmenting path in Ford-Fulkerson method and one of them is using of shortest path, therefore, I think the mentioned expression was something like above.

Some other ways to choose augmenting path:

1 - Fattest path : Implemented by using priority queue.

2 - DFS path : Implemented by using stack(DFS).

3 - Random path : Implemented by randomized queue.

https://www.coursera.org/learn/algorithms-part2/lecture/xmDao/running-time-analysis


Example where equivalence is easy but finding class representative is hard Suppose we have a class of objects (say graphs, strings), and an equivalence relation on these objects. For graphs this could be graph isomorphism. For strings, we could declare two strings equivalent if they are anagrams of each other.

I am interested in computing a representative for an equivalence class. That is, I want a function f() such that for any two objects x, y,
f(x) = f(y) iff x and y are equivalent.  (*)

For the example of anagrams, f(s) could sort letters in the string, ie. f('cabac') = 'aabcc'. For graph isomorphism, we could take f(G) to be a graph G' that is isomorphic to G and is the lexicoraphically first graph to have this property.

Now the question: Is there an example where the problem of determining whether two elements are equivalent is "easy" (poly time solvable), while finding a representative is difficult (i.e. there is no poly time algorithm to compute f() that satisfies (*)).

Ok, how about: numbers $x$ and $y$ are equivalent if either $x=y$, or both $x$ and $y$ have factorizations $x=pq$ and $y=pr$ where $p$, $q$, and $r$ are all prime and $p < \min(q,r)$. That is: products of two primes are equivalent when they share their smallest prime factor; other numbers are only equivalent to themselves.

It's easy to test whether two different numbers are equivalent: compute their gcd, test whether it's nontrivial, test whether the gcd is less than the cofactors, and test whether the gcd and its cofactors are all prime.

But it's not obvious how to compute a representative function $f$ in polynomial time, and if you add the requirement that $f(x)$ must be equivalent to $x$ then any representative function would allow us to factor most products of two primes (every one that isn't its own representative).

I suppose you can easily achieve that for virtually any problem of the type you describe.

Trivial example: Suppose objects are strings, and any $x$ is equivalent to only itself. Determining whether two elements are equivalent is always easy (it is simply equality). However, you can define $f()$ as your favorite injective hard function.


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?  Artificial examples coming directly from the proof of Ladner's theorem do not count.

Are any of these example provably NP-intermediate, assuming only some "reasonable" hypothesis?

Here's a collection of some of the responses of problems between P and NPC:

Factoring
Isomorphism problems: Graph Isomorphism [not NPC unless $\sum_2^p=\prod_2^p$] (via @Jeff Kinne), Graph Automorphism, Group Isomorphism, Automorphism, Ring Isomorphism and Automorphism (via @Joshua Grochow)
Computing the rotation distance between two binary trees or the flip distance between two triangulations of the same convex polygon (via @David Eppstein)
The Turnpike Problem of reconstructing points on line from distances (via @Suresh Venkat)
Problems arising from the Unique Games Conjecture (via @Moritz)
Discrete Log Problem and others related to cryptographic assumptions (via @Joe Fitzsimons)
Determining winner in parity games (via @mashca)
Determining who has the highest chance of winning a stochastic game (via @Peter Shor on MO)
Numbers in boxes problems (via @Joshua Grochow)
Agenda control for balanced single-elimination tournaments (via @virgi)
Knot triviality (via @JeffE)
(Assuming NEXP≠EXP) padded versions of NEXP-complete problems (via @Joshua Grochow)
Problems in TFNP (via @Marcos Villagra)
Intersecting Monotone SAT (via @András Salamon)
Minimum Circuit Size Problem (via @Eric Allender)
Deciding whether a given triangulated 3-manifold is a 3-sphere (via @Joe O'Rourke and @Peter Shor)
The Cutting Stock Problem with a constant number of object lengths (via @Suresh Venkat)
Monotone Self-Duality (via @Danu)
Planar Minimum Bisection (via @turkistany)
Pigeonhole Subset Sum (via @user834)
Square Root Sums (via @JeffE)
Deciding Whether a Graph Admits a Graceful Labeling (via @Oleksandr Bondarenko)
Gap version of the closest vector in lattice problem GapCVP$(\sqrt{n})$ (via @MCH)
The linear divisibility problem [known to be $\gamma$-complete but not NPC] (via @Oleksandr Bondarenko)
Finding the VC dimension (via @Mohammad al Turkistany)
Finding the minimum dominating set in a tournament (via @Mohammad al Turkistany)

A handful of natural problems are (promise) $\mathsf{BQP\:complete}$, and thus are not likely to be $\mathsf{NP\:complete}$ under the reasonable hypothesis that $\mathsf{NP}\not\subseteq\mathsf{BQP}$.
Adjusting the hypotheses to remove negative signs might negate the strength provided by interference, landing the problem in $\mathsf{NP}$ and not empowering it to be $\mathsf{BQP\:complete}$.
For example estimating an entry $(A^m)_{ij}$ of the $m^{th}$ power of a large, sparse matrix $A$ with $\mathcal{O}(\exp m)$ entries $A_{ij}\in\{-1,0,1\}$ is $\mathsf{BQP\: complete}$, as shown here.
I believe that when the entries $A_{ij}\in\{0,1\}$, e.g. when $A$ is an adjacency matrix of a large graph and $(A^m)_{ij}$ counts the number of $m$-length walks from vertex $i$ to vertex $j$, the estimation is amenable to Stockmeyer approximation, and thus likely in $\mathsf{AM}$, but still not $\mathsf{NP\:complete}$.


When does randomization speed up algorithms and it "shouldn't"? Adleman's proof that $BPP$ is contained in $P/poly$ shows that if there is a randomized algorithm for a problem that runs in time $t(n)$ on inputs of size $n$, then there also is a deterministic algorithm for the problem that runs in time $\Theta(t(n)\cdot n)$ on inputs of size $n$ [the algorithm runs the randomized algorithm on $\Theta(n)$ independent randomness strings. There must be randomness for the repeated algorithm that is good for all $2^n$ possible inputs]. The deterministic algorithm is non-uniform - it may behave differently for different input sizes.
So Adleman's argument shows that - if one doesn't care about uniformity - randomization can only speed-up algorithms by a factor that is linear in the input size.

What are some concrete examples where randomization speeds up computation (to the best of our knowledge)?

One example is polynomial identity testing. Here the input is an n-sized arithmetic circuit computing an m-variate polynomial over a field, and the task is to find out whether the polynomial is identically zero. A randomized algorithm can evaluate the polynomial on a random point, while the best deterministic algorithm we know (and possibly the best that exists) evaluates the polynomial on many points.

Another example is minimum spanning tree, where the best randomized algorithm by Karger-Klein-Tarjan is linear time (and the error probability is exponentially small!), while the best deterministic algorithm by Chazelle runs in time $O(m\alpha(m,n))$ ($\alpha$ is the inverse Ackermann function, so the randomization speed-up is really small). Interestingly, it was proved by Pettie and Ramachandran that if there's a non-uniform deterministic linear time algorithm for minimum spanning tree, then there also exists a uniform deterministic linear time algorithm.

What are some other examples?
Which examples do you know where the randomization speed-up is large, but this is possibly just because we haven't found sufficiently efficient deterministic algorithms yet?

I don’t know whether randomization “should” or “shouldn’t” help, however, integer primality testing can be done in time $\tilde O(n^2)$ using randomized Miller–Rabin, while as far as I know, the best known deterministic algorithms are $\tilde O(n^4)$ assuming GRH (deterministic Miller–Rabin) or $\tilde O(n^6)$ unconditionally (variants of AKS).

If you have an algorithm using randomisation, you can always replace it with a deterministic algorithm using pseudo-random numbers: Take the description of the problem, calculate a hash code, use that hash code as the seed for a good pseudo-random number generator. In practice, that's actually what is likely to happen when somebody implements an algorithm using randomisation.

If we leave out the hash code, then the difference between this algorithm and an algorithm using true randomisation is that I can predict the sequence of random numbers generated, and I could produce a problem such that the predicted random number applied to my problem will always make the worst possible decision. For example, for Quicksort with a pseudo-random pivot I could construct an input array where the pseudo-random pivot  will always find the largest possible value in the array. With true randomness that isn't possible.

With the hash code, it would be very difficult for me to construct a problem where the pseudo-random numbers produce worst outcomes. I can still predict the random numbers, but if I change the problem, the sequence of pseudo-random numbers changes completely. Still, it would be close to impossible for you to prove that I can't construct such a problem.


Finding the closest pair between two sets of points on the hypercube Given two subsets of the $d$-dimensional hypercube (i.e., $M, N \subseteq \{0,1\}^d$), I am looking for an algorithm which retrieves the points $m\in M, n\in N$ s.t. the hamming distance (or $L_1$-distance on the hypercube) $d_H(m,n)$ is minimal. The naive algorithm which checks just each pair needs $|M|\cdot |N| \cdot d$ time, is there any better result known?

For simplicity we may assume that $|M|=|N|=d$.

Just realized that you are asking for the case that $|M|=|N|=d$. Then you can do matrix multiplication, right? Write $M$ is a row matrix $X$, $N$ as a column matrix $Y$, negate the entries of $Y$, and compute the matrix $Z=XY$. Clearly, the $z_{i,j}$ is the Hamming distance between the $i$th point of $M$ and the $j$th point of $N$. According to the last breakthroughs this has running time $O(d^{2.3727})$ (but I have a 50,000 pages manuscript that shows how to do this matrix multiplication in $O(d^{2.3726999999})$ time by a really simple algorithm).

You can get similar effect if the matrices are not squares. I think Uri Zwick has a paper about fast matrix multiplication in this case.

In some sense, this is not too interesting - we want to avoid the $O(|M| * |N|)$  term. The improvements in the $d$ term are kind of meh, meh...

as in the comments this problem is generally closely connected to the same problem in a Hilbert space and algorithms there are nearly applicable. an example of this can be found in this paper by Arya et al [1] p29 where the authors benchmark their Hilbert space nearest neighbor algorithm using the boolean cube and the $L_\infty$ norm. their algorithm works on any $L_m$ Minkowski metric. as you point out (but wikipedia does not seem to nor do a lot of other refs) the Hamming distance metric is equivalent to the $L_1$ Minkowski space metric or "taxicab metric" on binary coordinates. their algorithm takes $ O(dn \log n)$ preprocessing time ($d$ dimensions) and logarithmic "query" time (per point). see also [2]

[1] An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions Arya et al, 30pp

[2] Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering Cazals


Finding outer face in plane graph (embedded planar graph) I have a planar graph, for which I have computed a combinatorial embedding and coordinates in the plane. So all my arcs are now oriented in the plane, respective to their end vertices.

Computing a list of all faces of the graph (as a list of oriented walks along their arcs) is fairly straightforward.

On the other hand, finding a simple way to pick the outer face out of the list of faces does not seem as easy: it is included in the list of faces, but since its orientation is "reversed" (i.e. relative to the outer region, rather than the inside of the graph boundary), all its properties in terms of neighbouring faces are identical to other faces.

Short of using plane coordinates to painstakingly identify the outer nodes/arcs of the graph, is there a more straightforward way to pick the outer face out of the list of faces using the combinatorial embedding (given as a table of arc successors in the oriented plane)?

Edit: Upon reading the comments, I realised that my wording was ambiguous (verging on the incorrect): while I have the combinatorial embedding and would like to use it (or the information derived from it), I also have coordinates derived from a drawing of that graph (hence the plane graph, not simply planar graph), ensuring that there is, indeed, a specific outer face.

What I meant to say is that I am looking for a method that would do more (or rather: less) than just looking at the coordinates of all faces and (for example), compute their orientation.

To be precise, the embedding and plane drawing give me:

a list of all faces (as an oriented walk of vertices).
for each arc: the face left and right of it.
for each vertex: an oriented walk of its ingoing/outgoing arcs (actually, my graph of interest is undirected, but that is probably not very relevant).

Edit 2: Despite the upvotes, the first comment does not really solve much (it essentially boils down to a recursive answer: "in order to find the outer face, use the leftmost vertex, then find the outer face", which isn't as trivial to solve as its commenter seemed to think.

@Zsbán provided what looks like the most efficient and elegant solution. Thanks!

First, suppose that your arcs are embedded to the plane as straight lines.  Then, the following three step algorithm works.

First, compute the leftmost vertex (as David Eppstein suggested).  This vertex will be on the unbounded face.

Second, among the arcs from that vertex, find the one whose slope is largest. This arc will be a side of the unbounded face.  (You must consider the slope; taking the arc with the leftmost destination vertex wouldn't work.  You may have to handle the case when this vertex is isolated somehow.)

Thirdly, take the face on the left hand side of this arc.  That face is the outer face.

If the edges aren't embedded as straight lines, then you need some extra information about the embedding.  Indeed, in any plane graph (with at least one cycle), you could just take an edge of the outer face and lift it around the whole embedding.  This changes the outer face, but doesn't move the vertexes, and doesn't change the cyclical orientation of arcs from the vertexes.

In particular, if the edges are open polygons given with the coordinates of the list of inner vertexes, then divide each such edge to a path and run the previous algorithm in the subdivided graph.  This may choose such an internal vertex in the first step.

A non-trivial method can be to calculate the convex hull of the vertices.
(This can only be used if the planar graph generated has a convex outer face, which is most likely the case for most of the graph drawing softwares.)

It seems to be an overkill though but it will give you the face exactly in form of a sequence of vertices given the coordinates of the vertices.
It takes $O(n\log n)$ time to find it. You can use the standard LEDA library to find it easily using its
subroutine.

However it can also be performed in linear time. Please refer to this.


Hardness of approximating chromatic number of triangle-free graphs The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs.

Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?

They can be 3-colored in polynomial time, no? I didn't check the literature but here is a simple approach: take a DFS tree of the graph and color a node $u$ at depth $d(u)$ with color $(d(u)\mod 3)$. This gives a proper coloring since (1) the neighborhood of each vertex is an independent and (2) two nodes $u,v$ such that $|d(u)-d(v)| \geq 2$ cannot be adjacent.


Constant in Komlos conjecture Given $n$ vectors $v_1,\dots,v_n\in\Bbb R^N$ with $\|v_i\|_2^2\leq1$ at every $i\in\{1,\dots,n\}$, Komlos conjecture states that, there is a $c\in\Bbb R$ (independent of $n,N$) such that at some $\epsilon\in\{-1,+1\}^n$, $$\Big\|\sum_{i=1}^n\epsilon_iv_i\Big\|_\infty<c.$$ What is best lower bound known for $c$?

Best upper bound is $c=O(\sqrt{\log n})$.

Is there a set of examples for $c=1+\delta$ for any $\delta>0$ where Komlos conjecture fails?

A simple way of obtaining a lower bound $c\ge\sqrt{2}$ is to consider pairs of vectors $u,v\in\mathbb{R}$. First of all, it makes sense to focus on pairs of unit vectors for which all $\{-1,1\}$-linear combinations are as long as possible (note that this is just an interesting special case, I'm not saying that it is opotimal in any way). This is achieved when $u,v$ are orthogonal, and by checking the possible rotations we find that $u=\frac{1}{\sqrt{2}}(1,1), v=\frac{1}{\sqrt{2}}(1,-1)$ show that $c$ must be at least $\sqrt{2}$.

This example can be generalized to the sets of vectors $V_k=\{2^{-\frac{k}{2}}v_{i,k}\ |\ 0\le i\le k\}\subseteq\mathbb{R}^{2^k}$, where the $j$-th coefficient $(v_{i,k})_j$ of $v_{i,k}$ is $1$ if the $i-th$ binary digit in $j$ is $0$, and $-1$ otherwise.

The $\infty$-norm of any $\{-1,1\}$-linear combination of the vectors in $V_k$ is $(k+1)2^{-\frac{k}{2}}$, which reaches its maximum $\frac{3}{2}$ at $k=2$, with the set of vectors

$V_2=\{\frac{1}{2}(1,1,1,1),\frac{1}{2}(1,1,-1,-1),\frac{1}{2}(1,-1,1,-1)\}$.

There may be better lower bounds, but this is a start.

There is no best lower bound, because c is an upper bound.
The best known upper bound is $O(\sqrt{\log n})$, as proved by Banaszczyk in 1998.


Find the optimal way to use combinations of summands to get the most sum with a limited number of summands I have a bit of a problem, I have a set of sums that add up to X, like so:

A: $i + j + k = X$

B: $t + z = X$

C: $z + z = X$

D: $j + j + k + k = X$

I have a limited number of summands so for example I have: 12 of $i$, 35 of $z$, 12 of $j$, and 18 of $k$, 21 of $t$.

What I need is an algorithm that will determine the best way to use those combinations so that I end up with the most complete sums of $X$

So in the example above using:

17 of combination $C$, 1 of combination $B$, and 12 of combination $A$, total 30 sums of $X$, 72 summands used

is worse then using:

21 of combination $B$, 7 of combination $C$, and 6 of combination $D$, total 34 sums of $X$, 80 summands used

EDIT:

To further explain:

using 21 of combination $B$ will "spend" 21 $t$ and 21 $z$ leaving us with: 12 of $i$, 14 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 7 of combination $C$ will "spend" 14 of $z$ (because it uses 2 summands of $z$ to be achieved) leaving us with: 12 of $i$, 0 of $z$, 12 of $j$, 18 of $k$, 0 of $t$

using 6 of combination $D$ will spend 12 of $j$ and 12 of $k$ (because it uses both of them twice) leaving us with: 12 of $i$, 0 of $z$, 0 of $j$, 6 of $k$, 0 of $t$

we can no longer make combinations that will add up to $X$ thus the algorithm is concluded.

The problem is a generalization of the set packing problem (exercise: why?), and therefore it is NP-hard even to approximate in a very weak sense.  See Maximum Set Packing and Maximum Clique in the compendium.

Try researching dynamic programming.  Dynamic programming provides the ability to iterate over a problem set that involves multiple equations.  Also, take a look at gaussian elimination.

If properly designed and implemented by setting the data up properly, gaussian elimination can intelligently reduce the number of combinations that the algorithm will need to look at.  In your example, a limit of 12 j was specified.  So, if one of the combinations looked at is 12 of A (which consists of i + j + k), then both i and j are exhausted since there are only 12 of each.  So, any other combination that uses i or j (like D which uses 2 of j) no longer needs to be evaluated since we know that this combination can not be used.


Natural CLIQUE to k-Color reduction There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. What I'm wondering is whether there is a reasonable direct reduction between these problems. Say, a reduction that I could explain to a friend fairly briefly without needing to describe an intermediate language like SAT.

As an example of what I'm looking for, here's a direct reduction in the reverse direction: Given G with $n$ and some $k$ (the number of colors), make a graph G' with $kn$ vertices (one per color per vertex). The vertices $v'$, $u'$ corresponding to vertices $v, u$ and colors $c, d$ respectively are adjacent if and only if $v \neq u$ and ($c \neq d$ or $vu \not \in G$). An $n$-clique in $G'$ has only one vertex per vertex in $G$, and the corresponding colors are a proper $k$-coloring of $G$. Similarly, any proper $k$-coloring of $G$ has a corresponding clique in $G'$.

Edit: To add some brief motivation, Karp's original 21 problems are proved NP-Complete by a tree of reductions where CLIQUE and Chromatic Number form the roots of major subtrees. There are some natural reductions between problems in the the CLIQUE subtree and the Chromatic Number subtree, but many of them are just as hard to find as the one I'm asking about. I'm trying to drill down on whether the structure of this tree shows some underlying structure in the other problems or if it is entirely a consequence of which reductions were found first, since there is less motivation to search for reductions between two problems when they are known to be in the same complexity class. Certainly the order had some influence, and parts of the tree can be rearranged, but can it be rearranged arbitrarily?

Edit 2: I continue to search for a direct reduction, but here is a sketch of the closest I've gotten (it should be a valid reduction, but has CIRCUIT SAT as a clear intermediary; it's somewhat subjective whether this is any better than composing two reductions as alluded to in the first paragraph).

Given $G, k$, we know that $\overline{G}$ can be $n-k+1$-colored with $k$ vertices all colored True iff $G$ has a $k$-clique. We name the original vertices of $G$ $v_1, \ldots, v_n$ and then add to $\overline G$ additional vertices: $C_{ij}$ with $1 \le i \le n$, $0 \le j \le k$. The key invariant will be that $C_{ij}$ can be colored True if and only if among vertices $\{v_1,\ldots, v_i\}$ there are at least $j$ vertices colored True. So, each $C_{i0}$ can be True. Then, $C_{ij}$ for $j > 0$ gets the color $C_{(i-1)j} \vee C_{(i-1)(j-1)} \wedge v_i$ where all non-true colors are treated as false. There is a $k$-clique in $G$ iff $C_{nk}$ can be colored True, so if we force that coloring, the new graph is colorable iff there was a $k$-clique in the original graph.

The AND and OR gadgets to enforce the relationships are much like the reduction from CIRCUIT SAT to 3-COLOR, but here we include a $K_{n-k+1}$ in our graph, pick vertices T, F, and Ground, and then connect all others to everything but the $v_i$s; this assure that the $C_{ij}$s and the other gadgets receive only 3 colors.

Anyway, the $\overline G$ part of this reduction feels direct, but the use of AND/OR gates is much less direct. The question remains, is there a more elegant reduction?

Edit 3: There have been a few comments about why this reduction would be hard to find. CLIQUE and k-Color are indeed quite different problems. Even without a reduction, though, an answer that details why the reduction is hard in the one direction but possible in the other would be very helpful and contribute a lot to the problem.

Given a graph $G$ and a number $k$, such that you want to know whether $G$ contains a $k$-clique, let n be the number of vertices in $G$. We construct another graph $H$, such that $H$ is $n$-colorable if and only if $G$ has a $k$-clique, as follows:

(1) For each vertex $v$ in $G$, make an $n$-clique of vertices $(v,i)$ in $H$, where $i$ ranges from $1$ to $n$.

(2) Add one additional vertex $x$ to $H$.

(3) For each triple $\{x,y,z\}$ of vertices in $H$, where $y=(v,i)$ and $z=(u,j)$, test whether one of the following conditions holds: either $u\ne v$ and $i=j$, or $u$ and $v$ are nonadjacent vertices in $G$ with $\max(i,j)\le k$. If either of these two things is true, add another $n$-clique to $H$. Within this clique, select three vertices $x'$, $y'$, and $z'$. Connect $x$ to every vertex in the clique except for $y'$ and $z'$; connect $y$ to every vertex in the clique except for $x'$ and $z'$; and connect $z$ to every vertex in the clique except for $x'$ and $y'$.

The gadgets added in step (3) prevent the triple of vertices $x$, $y$, and $z$ from all being given the same color as each other in a valid coloring of $H$. The clique in $G$ can be recovered from a coloring of $H$ as the set of vertices $(v,i)$ that are in the same color class as $x$ and that have $i\le k$.

?? coloring and clique finding have been known to be tightly coupled for decades via graph theory (possibly even in the 60s?) even not through SAT as an intermediary (which became typical after the Cook proof in 1971). believe there are algorithms based on the following basic property:

  If G contains a clique of size k, then at least k colors are needed to color that clique; in other words, the chromatic number is at least the clique number:
  $\chi(G) \ge \omega(G).\,$

not sure of exact refs but [1,2] are good places to start, an exact algorithm or ref is at least likely cited in these books.

[1] Cliques, coloring, & satisfiability, 2nd DIMACS challenge

[2] Dimacs vol 26: Cliques, coloring and satisfiability


Fastest way to find an s-t min-cut from an s-t max-flow? Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity.

How could I use a sparse s-t flow to find an s-t min-cut in time proportional to the size of the flow and the number of my nodes, for the sparse/low-volume max-flow case?

If you don't use the flow per se, but use the Ford-Fulkerson algorithm (or some version, like Edmonds-Karp), you can get both the max-flow and the min-cut directly as a result. When looking for augmenting paths, you do a traversal, in which you use some form of queue of as-yet-unvisited nodes (in the Edmonds-Karp version, you use BFS, which means a FIFO queue). In the last iteration, you can't reach $t$ from $s$ (this is the termination criterion, after all). At this point, the set of nodes you reached forms the $s$-part of the cut, while the nodes you didn't reach form the $t$-part.

The leaf nodes of your traversal tree form the “fringe” of the $s$-part, while the nodes in your traversal queue form the fringe of the $t$-part, and what you want is the set of edges from the $s$-fringe to the $t$-fringe. This can also easily be maintained during traversal: Just add an edge to the cut when it is examined, and leads to an unvisited node, and remove it if it is traversed (so its target becomes visited). Then, once Ford-Fulkerson is finished, you'll have your min-cut (or, rather, one of them) right there. The running time will be (asymptotically) identical to Ford-Fulkerson (or Edmonds-Karp or whatever version you're using), which should give you what you were looking for.

Is there a quick reference for the definition of a sparse s-t flow?

In the general case, having the max-flow it is quite easy to determine the min-cut, via the max-flow , min-cut theorem. The edges that are fully saturated form a cut set, so by selecting one vertex for each such edge, one can form a min-cut. Trivially, this is O(m) in the worst case, and also if one makes the running time output-sensitive, then the number of edges in the flow or even better, the number of saturated edges in the flow, always is an upper bound on the running time of the algorithm for finding the min-cut from the max-flow. So if you have a modification that finds those sparse s-t flows in linear time in the size of the flow, finding the min-cut won't change the algorithm's runtime asymptotically.


Random point in a d-dimensional ball I would like to know if there any algorithm to pick a random grid point inside a d-dimensional ball with a given radius R.  And if there any algorithm to pick a random arbitrary point inside a d-dimensional ball with a given radius R.

Thanks.

For the latter, this discussion is a good starting point.  For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.

In view of a circle with center $(a,b)$ and radius $r$, the points $(x,y)$ on the circle fulfill
$(x-a)^2 + (y-b)^2 = r^2$.
In parametric form, the points are given by $x=a+r\cos\phi$ and $y=b+r\sin\phi$ with angle $\phi$ between 0 and $2\pi$.

Thus finding a random point in the circle is to choose an angle $\phi$ uniformly at random and a number $d$ with $0\leq d\leq r$ uniformly at random.


Is it known if $CFL \subseteq NSPACE(o(log^2(n)))$? $CFL$ is the class of context-free languages.

  Question

  Is $CFL$ known to be solvable in $o(log^{2}(n))$ non-deterministic space?  What about $DCFL$?

Yes. This is Theorem 4 in the following paper.

Philip M. Lewis II, Richard Edwin Stearns, Juris Hartmanis:
Memory bounds for recognition of context-free and context-sensitive languages. SWCT (FOCS) 1965: 191-202.

Edit: I am sorry. My answer is not helpful. I missed the "small o". Stupid...
I am not sure what to do. Delete the answer?