Tag Info

47

SAT, CP, SMT, (much of) ASP all deal with the same set of combinatorial optimisation problems. However, they come at these problems from different angles and with different toolboxes. These differences are largely in how each approach structures information about the exploration of the search space. My working analogy is that SAT is machine code, while the ...

27

It seems the issue is the kind of reductions used for each of them, and they are using different ones: they probably mean "$\mathsf{NP}$-hard w.r.t. Cook reductions" and "$\mathsf{NP}$-complete w.r.t. Karp reductions". Sometimes people use the Cook reduction version of $\mathsf{NP}$-hardness because it is applicable to more general computational problems (...

19

A "gadget" is a small specialized device for some particular task. In NP-hardness proofs, when doing a reduction from problem A to problem B, the colloquial term "gadget" refers to small (partial) instances of problem B that are used to "simulate" certain objects in problem A. For example, when reducing 3SAT to 3-COLORING, clause gadgets are small graphs ...

17

A calculus is just a system of reasoning. One particular calculus (well, actually two closely related calculi: the differential calculus and the integral calculus) has become so widespread that it is just known as "calculus", as if it were the only one. But, as you have observed, there are other calculi, such as the lambda calculus, mu calculus, pi calculus, ...

17

It's common to say that $f$ and $g$ commute with respect to composition (where the property is known as commutativity). See, e.g., http://en.wikipedia.org/wiki/Function_composition.

17

I'm not sure, but you might be talking about what has been termed incremental computation. The key idea behind incremental computation is to program in a way such that the program responds to input changes by updating its output while only re-evaluating those portions of the program affected by the change. Incremental computing is feasible in situations ...

16

perfect graphs were first motivated by information transmission theory originating with Shannon ie Shannon Capacity of graphs. they are called "perfect" by Berge because they can be used to model a noiseless or "perfect" information channel wrt transposition errors in transmission called "confounding". from intro in [3] which also has a very detailed history ...

14

Goodrich's "Randomized Shellsort: A Simple Oblivious Sorting Algorithm" has a discussion of data-oblivious sorting. Sorting networks are data-oblivious, but impractical in general, as I understand it.

13

A formal definition of Gadgets for NP optimization reductions appears here: L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson. Gadgets, Approximation, and Linear Programming. SIAM J. on Computing, 29(6):2074-2097, 2000

13

1) The only non-structural rule is resolution (on atoms). $$\varphi\lor C, \psi\lor \overline{C} \over \varphi\lor \psi$$ However a rule by itself doesn't give a proof system. See part 3. 2) Think about it this way: is Gentzen's sequent calculus PK complete if we are using some other set of connectives in place of $\{\land, \lor, \lnot\}$? The logical ...

12

Recursion is an abstract concept. Talking about whether or not it has in-place semantics is nonsense. (Unless of course the language specifies recursion semantics.) This idea is related to how it is nonsense to talk about the speed of a language. How recursion is implemented is another question. For example, a compiler might perform tail call optimization ...

11

This is called the (linear) assignment problem. It can be solved efficiently through linear programming over the Birkhoff polytope.

10

Computer science (especially theory B) has many connections to category theory, and that is the usual context for lifting. The basic idea is that you might have two objects $X$ and $Y$ that interact in a very intuitive way for you, and so it is easy to define a good morphism $f: X \rightarrow Y$. You might have a more complicated object $Z$ that is easy to ...

10

What proof system is being considered when discussing resolution? Is it just the resolution rule? What are the other rules? I discuss resolution in the context of "clauses", which are sequents made up of only literals. A classical clause would look like $$A_1,\ldots,A_n \to B_1,\ldots,B_m$$ But we can also write it as $${} \to \bar{A}_1,\ldots,\bar{A}_n, ... 9 In a rule Aβ→γβ, β is called the context because it does not change by applying the rule. Applying a rule Aβ→γ changes the β part completely, and therefore β is not a context at all. In this case, β does not have a name. It is nothing more than one of the many substrings of the left-hand side of the rule Aβ→γ. If I have to call β as something, I would ... 9 I don't know if these graphs have a common name. But I think, one would call vertices with no outgoing edge rather a sink than a root. This paper studies acyclic orientations of grid graphs. They call an orientation, which would correspond to the graphs you consider, acyclic orientations with a unique sink. 9 I believe the most standard term is complete multipartite graph. 9 The problem you describe has definitely been considered (I remember discussing it in grad school, and at the time already it had been discussed long before then), though I can't point to any particular references in the literature. Possibly because it is linearly equivalent to uncolored graph isomorphism, as follows (this is true even for canonical forms). ... 8 Although not for sorting, note that there are algorithms that may naturally be described using recursion but that do not require storage of a call stack. For instance, quickselect can be described as a modified version of quicksort that makes only one of the two recursive calls of quicksort; however, using tail recursion for this call avoids the need for a ... 8 The notation m^{O(1)} just denotes the set of functions of polynomial growth rate, so that would be indeed confusing. The class of functions computable in polynomial time is usually denoted \mathsf{FP}. 8 How about this: Call your graphs simply (K_1 + K_2)-free graphs, where K_n is the complete graph with n vertices, + stands for disjoint union, and H-free means without H as an induced subgraph. 8 Some of the very early work on complexity theory used a sequential time model -- that is, rather than studying the worst-case runtime of the TM that can produce the correct output on an arbitrary input, they studied machines that would run infinitely and enumerate the correct output for each input in lexicographic order. The complexity of the machine was ... 7 The two inference rules are different, because the first requires that x:T_1 is the only assumption, while the second allows side assumptions. This can have subtle effects of the consequence relation for the type theory prevents the type theory from modelling weakening by having as the hypothesis rule:$$ \frac{}{\Gamma, x:A \vdash x:A}  In your English ...

7

Calculus refers to systematic methods of treating problems by a special system of algebraic notations, generally a method of calculation.

7

In general I agree with usul's summary: for upper bounds $2^{\sqrt{n}}$ is certainly at most exponential, and for lower bounds it's more context-dependent and less clear. Let me offer a couple more examples from different contexts, and provide the term "moderately exponential" for your consideration. In the literature on graph isomorphism (which is ...

7

Niel De Beaudrap's point is an important one: a complexity class is defined with respect to a machine model. But if I were to re-interpret your question as: Can the complexity of a problem differ greatly in different computational models ? Then the answer is yes. JeffE's answer to my earlier question about decision tree complexity presents an example of ...

7

I believe he may be referring to this paper: NAMING AND SYNCHRONIZATION IN A DECENTRALIZED COMPUTER SYSTEM.

7

Such algebras are called functionally complete. Also, what you call terms are actually called polynomials. In standard terminology, term operations have a more restricted definition that allows variables and the basic operations $f_i$, but not constants from $E$. Algebras that satisfy the stronger condition that every operation is represented by this kind of ...

7

One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with randomized pivoting rules, due to Friedmann, Hansen, and Zwick. The lower bounds rely on lower bounds for policy iteration algorithms for parity games, which are ...

6

Even when stored very efficiently, vertices with zero degree must be stored in some nonzero space (otherwise, how can we say they even exist)? That said, they can be stored and searched more efficiently than $O(|V| + |E|)$ using similar ideas to what you describe. For example, you could just take a standard data structure for storing graphs and store the ...

Only top voted, non community-wiki answers of a minimum length are eligible