| 1. |
- Bodirsky, Manuel, et al.
(författare)
-
Essential Convexity and Complexity of Semi-algebraic Constraints
- 2012
-
Ingår i: Logical Methods in Computer Science. - : International Federation for Computational Logic. - 1860-5974. ; 8:4
-
Tidskriftsartikel (refereegranskat)abstract
- Let \Gamma be a structure with a finite relational signature and a first-order definition in (R;*,+) with parameters from R, that is, a relational structure over the real numbers where all relations are semi-algebraic sets. In this article, we study the computational complexity of constraint satisfaction problem (CSP) for \Gamma: the problem to decide whether a given primitive positive sentence is true in \Gamma. We focus on those structures \Gamma that contain the relations \leq, {(x,y,z) | x+y=z} and {1}. Hence, all CSPs studied in this article are at least as expressive as the feasibility problem for linear programs. The central concept in our investigation is essential convexity: a relation S is essentially convex if for all a,b\inS, there are only finitely many points on the line segment between a and b that are not in S. If \Gamma contains a relation S that is not essentially convex and this is witnessed by rational points a,b, then we show that the CSP for \Gamma is NP-hard. Furthermore, we characterize essentially convex relations in logical terms. This different view may open up new ways for identifying tractable classes of semi-algebraic CSPs. For instance, we show that if \Gamma is a first-order expansion of (R;*,+), then the CSP for \Gamma can be solved in polynomial time if and only if all relations in \Gamma are essentially convex (unless P=NP).
|
|
| 2. |
- Bodirsky, Manuel, et al.
(författare)
-
Horn versus Full First-order : Complexity Dichotomies in Algebraic Constraint Satisfaction
- 2012
-
Ingår i: Journal of logic and computation (Print). - : Oxford University Press (OUP). - 0955-792X .- 1465-363X. ; 22:3, s. 643-660
-
Tidskriftsartikel (refereegranskat)abstract
- We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove definability dichotomy theorems of the following form: for every first-order expansion Gamma of Delta, either Gamma has a quantifier-free Horn definition in Delta, or there is an element d of Gamma such that all non-empty relations in Gamma contain a tuple of the form (d,...,d), or all relations with a first-order definition in Delta have a primitive positive definition in Gamma. The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods.
|
|
| 3. |
- Bodirsky, Manuel, et al.
(författare)
-
Integer programming with 2-variable equations and 1-variable inequalities
- 2009
-
Ingår i: INFORMATION PROCESSING LETTERS. - : Elsevier BV. - 0020-0190. ; 109:11, s. 572-575
-
Tidskriftsartikel (refereegranskat)abstract
- We present an efficient algorithm to find an optimal integer solution of a given system of 2-variable equalities and I-variable inequalities with respect to a given linear objective function. Our algorithm has worst-case running time in O(N-2) where N is the number of bits in the input.
|
|
| 4. |
|
|
| 5. |
- Bodirsky, Manuel, et al.
(författare)
-
Semilinear Program Feasibility
- 2009
-
Ingår i: Automata, Languages and Programming. - Berlin / Heidelberg : Springer. - 9783642029295 ; , s. 79-90
-
Konferensbidrag (refereegranskat)abstract
- We study logical techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems (CSPs). For the fundamental algebraic structure where are the real numbers and L 1,L 2,... is an enumeration of all linear relations with rational coefficients, we prove that a semilinear relation R (i.e., a relation that is first-order definable with linear inequalities) either has a quantifier-free Horn definition in Γ or the CSP for is NP-hard. The result implies a complexity dichotomy for all constraint languages that are first-order expansions of Γ: the corresponding CSPs are either in P or are NP-complete depending on the choice of allowed relations. We apply this result to two concrete examples (generalised linear programming and metric temporal reasoning) and obtain full complexity dichotomies in both cases.
|
|
| 6. |
- Ghisletta, Paolo, et al.
(författare)
-
On the use of growth models to study normal cognitive aging
- 2020
-
Ingår i: International Journal of Behavioral Development. - : SAGE Publications. - 0165-0254 .- 1464-0651. ; 44:1, s. 88-96
-
Tidskriftsartikel (refereegranskat)abstract
- Growth models (GM) of the mixed-effects and latent curve varieties have become popular methodological tools in lifespan research. One of the major advantages of GM is their flexibility in studying individual differences in change. We scrutinized the change functions of GM used in five years of publications on cognitive aging. Of the 162 publications that we identified, 88% test linear or quadratic polynomials, and fewer than 5% apply functions that are nonlinear in their parameters, such as exponential decline. This apparent bias in favor of polynomial decomposition calls for exploring what conclusions about individual differences in change are likely to be drawn if one applies linear or quadratic GMs to data simulated under a conceptually and empirically plausible model of exponential cognitive decline from adulthood to old age. Hence, we set up a simulation that manipulated the rate of exponential decline, measurement reliability, number of occasions, interval width, and sample size. True rate of decline and interval width influenced results strongly, number of occasions and measurement reliability exerted a moderate effect, and the effects of sample size appeared relatively minor. Critically, our results show that fit statistics generally do not differentiate misspecified linear or quadratic models from the true exponential model. Moreover, power to detect variance in change for the linear and quadratic GMs is low, and estimates of individual differences in level and change can be highly biased by model misspecification. We encourage researchers to also consider plausible nonlinear change functions when studying behavioral development across the lifespan.
|
|
| 7. |
- Li, Shu-Chen, et al.
(författare)
-
Ebbinghaus Revisited : Influences of the BDNF Val66Met Polymorphism on Backward Serial Recall Are Modulated by Human Aging.
- 2010
-
Ingår i: Journal of cognitive neuroscience. - Cambridge, Mass. : MIT Press - Journals. - 0898-929X .- 1530-8898. ; 22:10, s. 2164-2173
-
Tidskriftsartikel (refereegranskat)abstract
- Abstract The brain-derived neurotrophic factor (BDNF) plays an important role in activity-dependent synaptic plasticity, which underlies learning and memory. In a sample of 948 younger and older adults, we investigated whether a common Val66Met missense polymorphism (rs6265) in the BDNF gene affects the serial position curve-a fundamental phenomenon of associative memory identified by Hermann Ebbinghaus more than a century ago. We found a BDNF polymorphism effect for backward recall in older adults only, with Met-allele carriers (i.e., individuals with reduced BDNF signaling) recalling fewer items than Val homozygotes. This effect was specific to the primacy and middle portions of the serial position curve, where intralist interference and associative demands are especially high. The poorer performance of older Met-allele carriers reflected transposition errors, whereas no genetic effect was found for omissions. These findings indicate that effects of the BDNF polymorphism on episodic memory are most likely to be observed when the associative and executive demands are high. Furthermore, the findings are in line with the hypothesis that the magnitude of genetic effects on cognition is greater when brain resources are reduced, as is the case in old age.
|
|
| 8. |
- Schmiedek, Florian, et al.
(författare)
-
Within-person structures of daily cognitive performance differ from between-person structures of cognitive abilities
- 2020
-
Ingår i: PeerJ. - : PeerJ. - 2167-8359. ; 8
-
Tidskriftsartikel (refereegranskat)abstract
- Over a century of research on between-person differences has resulted in the consensus that human cognitive abilities are hierarchically organized, with a general factor, termed general intelligence or g, uppermost. Surprisingly, it is unknown whether this body of evidence is informative about how cognition is structured within individuals. Using data from 101 young adults performing nine cognitive tasks on 100 occasions distributed over six months, we find that the structures of individuals' cognitive abilities vary among each other, and deviate greatly from the modal between-person structure. Working memory contributes the largest share of common variance to both between- and within-person structures, but the g factor is much less prominent within than between persons. We conclude that between-person structures of cognitive abilities cannot serve as a surrogate for within-person structures. To reveal the development and organization of human intelligence, individuals need to be studied over time.
|
|
