# Tag Info

49

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 (...

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

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 ...

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, ... 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 ... 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 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 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 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 ...

7

In mathematics we would say $f$ is an idempotent function. It's a widely known term and I suppose most TCS people should also recognize it.

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 ...

6

It's difficult to know what you mean because you're staying at a level that's so high that there's nothing interesting. Specific cases could be very interesting, but the basic idea that having computed a function for one input can make it easier to compute it for other inputs is too general. It may be that you have a function $f$ such that having computed $... 6 See the paper Varunkumar Jayapaul, J. Ian Munro, Venkatesh Raman, Srinivasa Rao Satti (2015), "Sorting and Selection with Equality Comparisons", Proc. WADS 2015, LNCS 9214, pp. 434–445, doi:10.1007/978-3-319-21840-3_36 It is exactly about the problem you ask, finding the equivalence classes of an equivalence relation by querying the equivalences of pairs ... 6 One example (from my research field) is analysis of dynamical systems: in a (linear) dynamical system, you are given a matrix$A\in {\mathbb Q}^{d\times d}$and you reason about various properties of$A^n$. For example, the Kannan-Lipton Orbit Problem asks, given two vectors$s,t\in \mathbb Q^d$, whether there exists$n$such that$A^ns=t$. These types of ... 5 FWIW, your problem is hard to approximate within a multiplicative factor of$n^{1-\epsilon}$for any$\epsilon>0$. We show that below by giving an approximation-preserving reduction from Independent Set, for which the hardness of approximation is known. Reduction from Independent Set Let undirected graph$G=(V,E)\$ be an instance of Independent Set. ...

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