51

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


20

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.


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

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


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

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


8

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


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.


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

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

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

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

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

Here is another attempt at a more comprehensive answer. Your question already contains the formal definition of FO-rewritability, which at its core says that you can reduce a query answering problem: The problem $D\cup\Sigma\models Q$ is being reduced to a problem $D\models Q_\Sigma$. Several noteworthy things are happening here. The original problem is ...


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


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

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

Looks to me like some additional restrictions on a topological sort: https://en.m.wikipedia.org/wiki/Topological_sorting . Also git already supports this operation for instance git rev-list --topo-order .


4

Your question would probably fit better on MathsStackExchange, but here is an answer. I don't think there is any specific name for your definition. Since any semigroup is isomorphic to a transformation semigroup, your question is about finitely generated semigroups that are quotients of the semigroup $S_n$ with presentation $$ \langle a_1, \ldots, a_n \mid ...


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