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

# Tag Info

### 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 ...
• 18.7k
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 ...
• 10.3k
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.
• 1,713
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 ...
• 31.7k
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 ...
• 35.6k
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.
• 661

### 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 ...
• 2,183

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

### 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 ...
• 35.6k

### 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 ...
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 ...
• 14.7k

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 ...
• 1,026
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 ...
• 5,366

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