Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with descriptive-complexity
Search options not deleted
user 109
Descriptive complexity classifies problems based on how hard it is to express the problem in some logical formalism.
6
votes
1
answer
168
views
Non-interesting numbers via resource-bounded properties?
There is an old joke about the smallest non-interesting number being interesting in itself (I have heard it attributed to Richard Hamming). This is then used to justify the argument that every number …
- 19.2k
16
votes
Why do relational databases work at all, given the theoretical exponential complexity of ans...
There are large classes of queries which are "easy", even in the worst case. In particular, if the class of queries contains conjunctive queries only and each query has bounded width (for instance tr …
- 19.2k
20
votes
0
answers
505
views
Model-checking for three-variable logics and restricted structures
Denote the $k$-variable fragment of logic $L$ by $L^{(k)}$. The model-checking problem for a logic $L$ with respect to a class of structures $C$, denoted $MC(L,C)$, is the decision problem
$MC(L, …
- 19.2k
41
votes
6
answers
2k
views
Is there a logic without induction that captures much of P?
The Immerman-Vardi theorem states that PTIME (or P) is precisely the class of languages that can be described by a sentence of First-Order Logic together with a fixed-point operator, over the class of …
- 19.2k
12
votes
3
answers
294
views
Is there a natural restriction of VO logic which captures P or NP?
The paper
Lauri Hella and José María Turull-Torres,
Computing queries with higher-order logics,
TCS 355 197–214,
2006.
doi: 10.1016/j.tcs.2006.01.009
proposes logic VO, variable-order logic. This …
- 19.2k