50

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


28

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


18

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

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


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.


13

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

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


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


9

I believe the most standard term is complete multipartite graph.


9

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.


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

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


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

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


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

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

You seem to be asking about incremental computation. In general, it takes the following form: we have a function $f$, which is expensive to compute. We have computed $f(x)$ for a single input $x$. Now we want to compute $f(x')$, for a second input $x'$ where $x'$ is somehow "similar" to $x$. It'd be nice if we could take advantage of the fact that we ...


4

It's called finding a minimal model of a Horn formula. This model is unique because the intersection of two models of a Horn formula is itself a model. In fact, [Horn, On sentences which are true of direct unions of algebras, 1951] proved the following: A boolean function can be expressed as a conjunction of Horn clauses if and only if its set of models is ...


4

Another well known example of how a Turing complete computational model can lead to a time complexity blow-up is 2 Counter Automata (2CA) A 2CA is equipped with two registers that can store an unbounded nonnegative integer and can execute only simple instructions decrement/increment the counters, conditional jumps (after checking if a counter is zero), ...


4

I think these are all pretty standard, but context matters. I don't think there's a clear answer to your "particular" question, and I'll try to explain why. Usually our usage of these terms comes from algorithm complexity. In terms of time complexity of algorithms, there are two definitions of exponential: EXPTIME: $2^{n^{O(1)}}$. That is, $2$ raised to a ...


4

Many times, we can use Linearization of a function to approximate values near a point to reasonable accuracy. A single answer is generated with expensive algorithms (e.g., $\sqrt{2}\approx1.41421...$) then nearby answers are generated from that answer with a simple algorithm (e.g., $\sqrt{x}\approx0.35355x+0.70711, x\approx2$. Using expensive algorithms, $\...


4

This is basically what dynamic data structures and streaming algorithms are about. A few links, off the top of my Google: High performance data structure for streaming graphs Mihai Patrascu's thesis Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search Dynamic shortest paths and transitive closures For example, a dynamic data structure ...


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