Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
51 votes

Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming

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 ...
user avatar
17 votes
Accepted

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

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 ...
user avatar
17 votes
Accepted

Terminology for f(g(x)) = g(f(x))

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.
user avatar
  • 1,713
10 votes
Accepted

Can complexities differ w.r.t. different computational models?

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 ...
user avatar
9 votes
Accepted

Graph isomorphism with equivalence relation on the vertex set

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 ...
user avatar
9 votes
Accepted

Adjective for: algorithm that outputs its input if it is one of its outputs?

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.
user avatar
8 votes

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

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 ...
user avatar
  • 2,183
8 votes

What's "pseudo time" when used in comparison with semaphores

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

Is it right to call $2^{\sqrt{n}}$ "exponential"?

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 ...
user avatar
7 votes

Are there any intersections between Theory A and Theory B?

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 ...
user avatar
7 votes
Accepted

Terminology about computation and Finite algebra

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 ...
user avatar
6 votes

Are there any intersections between Theory A and Theory B?

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 $...
user avatar
  • 5,261
6 votes
Accepted

On partitioning a collection into equivalence classes

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/...
user avatar
6 votes

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

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 ...
user avatar
5 votes

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

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$. ...
user avatar
  • 10.3k
4 votes
Accepted

What is the name of this algorithm on direct acyclic graph?

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-...
user avatar
  • 1,357
4 votes

Is there a notion of "sequential" idempotence?

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 ...
user avatar
  • 4,721
4 votes

Can complexities differ w.r.t. different computational models?

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 ...
user avatar
4 votes

Is it right to call $2^{\sqrt{n}}$ "exponential"?

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 ...
user avatar
  • 7,022
4 votes

What is First-Order Rewritable (and FO-Query)?

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: ...
user avatar
  • 454
4 votes

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

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 ...
user avatar
4 votes

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

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...$) ...
user avatar
  • 141
3 votes

Graph isomorphism with equivalence relation on the vertex set

I read your last comment in the Joshua's correct answer; if you need to transform EQ-GI to colored GI (i.e. you are in trouble with the colors assigned to the equivalence classes) you can use the ...
user avatar
2 votes

Is it a Known Concept to Compute an Algorithm Once and Re-Interpret Answer for Different Inputs

This paper describes a new form of incremental computation: taking derivatives on data-type-valued functions (e.g. List-valued functions). http://www.informatik.uni-marburg.de/~pgiarrusso/papers/...
user avatar
2 votes

Are there any intersections between Theory A and Theory B?

As far as I understand it, linear logic and "implicit complexity theory" use tools that are often found in Theory B (type theory, theory of programming languages, etc.) to capture and study complexity ...
user avatar
2 votes

What is the etiquette of naming concepts after people?

It is best to spend some time researching to ensure that you associate the correct person with the idea and mention related ideas by others. You wouldn't want a misnomer to be called a Squark - like ...
user avatar
  • 121
1 vote
Accepted

Constraint terminology

This is not clear from your question, but I am going to assume that the groups are disjoint. I.e. $C = \bigcup_i C_i$ and $C_i \cap C_j = \emptyset$ for every $i \neq j$. Then the collection of sets $\...
user avatar
1 vote

Constraint terminology

To be clear that I understand the context, I'm going to first reproduce you situation worded differently. Consider a sequence of sets, $C_i$, and a target function, $f$. Let $\cup C_i=C$. We wish ...
user avatar
1 vote

what does "lifting" mean?

There is also Hensel lifting in modular arithmetic, that allows you to relate roots of a polynomial over a ring of integers modulo prime $p$ to roots of the same polynomial over integers modulo higher ...
user avatar

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