Tag Info

1

Finding mixed cycles in a mixed graph is equivalent to finding elementary directed cycles (of length >=3) in the corresponding directed graph. The corresponding directed graph is obtained from the mixed graph by replacing each undirected edge by two directed edges pointing in opposite directions. Proof: (1) Each elementary directed cycle (of length >=3) in ...

6

Rabin and Scott introduced the nondeterministic finite automata with their research paper published in IBM journal, April 1959. In the paper they mentioned: we have adopted an even simpler form of the definition by doing away with a complicated output function and having our machines simply give “yes” or “no” answers. This was also used by Myhill, ...

10

Here is what Odifreddi says on the issue: "Our model of a Turing machine is deterministic, in the sense that the instructions are required to be consistent (at most one of them is applicable in any given situation). Randomizing elements in computing devices were introduced early on by Shannon [1948] and De Leeuw, Moore, Shannon and Shapiro ...

23

I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their Decision Problems, 1959. Rabin's Turing Award citation also suggests that Rabin and Scott introduced nondeterministic machines.

2

This is a special case of non-monotone submodular maximization with a cardinality constraint, and constant factor approximation algorithms are known. For example, Feldman, Naor, and Schwartz get a factor 1/e, and improve this further in a subsequent paper with Buchbinder.

11

It's NP-complete for $k=3$ by a reduction from betweenness. In the betweenness problem, one is given $n$ items to be totally ordered, and constraints on some triples of items forcing one item of the triple to be between the other two. In your problem, the same constraint can be forced by forbidding all the subsequences on three elements that do not place the ...

1

Combinatorial game theory and topics thereof has received a lot of attention in modelling and verification of reactive systems. I would draw your attention to this nice reference for more information.

5

I think Kaveh's comment is the correct answer: applications? We don't need no applications. But despite all that, combinatorial game theory does appear to have some applications in error correcting codes. See Conway and Sloane, "Lexicographic codes: Error-correcting codes from game theory", IEEE Trans. Inf. Th. 1986. More simply, if you are willing to ...

6

The directed versions are much harder. A survey by Nutov available on his web page is a good starting point. http://www.openu.ac.il/home/nutov/Survivable-Network.pdf

7

The only known proper containment is still $L \subsetneq PSPACE$, though they are all widely believed to be different. All the rest are still wide-open. The recent work on Fine-Grained Complexity", like the Edit Distance result of Backurs and Indyk, side-steps the fact that we can't prove proper containments, like $P\neq NP$. In particular, SETH is a ...

7

Up to my knowledge the current "limits" have been settled in: Stefan Porschen, Tatjana Schmidt, Ewald Speckenmeyer, Andreas Wotzlaw: XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics 167: 1-14 (2014) See also Schmidt's Thesis: Computational Complexity of SAT, XSAT and NAE-SAT for linear and mixed Horn CNF formulas Theorem 29. XSAT ...

1

These 3 books on arithmetic complexity don't seem to have been mentioned till now, (Amir Shpilka, Amir Yehudayoff) http://www.cs.tau.ac.il/~shpilka/publications/SY10.pdf (Xi Chen, Neeraj Kayal, and Avi Wigderson) http://research.microsoft.com/apps/pubs/default.aspx?id=154351 (Neeraj Kayal and Ramprasad Saptharishi) ...

1

A reduction from planar 3-SAT should work. At least if the disks need not have equal size. Start by creating a triangular grid of disks (shown in blue in the figure). We enforce these disks to be in the cover by not covering one of their points by any other disks. Now what remains is to cover the gaps left in between disks by a minimal number of disks. ...

1

If I arrange the disks into a spiral pattern then the problem is NP-hard. It may be even harder in your general case. This would be a variation on the polygon covering problem. See https://en.wikipedia.org/wiki/Polygon_covering

Top 50 recent answers are included