Passer au contenu principal

Recherche

Afficher tous les résultats pour

Accueil

Publication

Ramsey-Type Results For Semi-Algebraic Relations

À propos
Confidentialité
Mentions légales

Copyright © 2025 EPFL, tous droits réservés

Graph Chatbot

János Pach
2014

Résumé

A k-ary semi-algebraic relation E on R-d is a subset of R-kd, the set of k-tuples of points in R-d, which is determined by a finite number of polynomial inequalities in kd real variables. The description complexity of such a relation is at most t if d, k

Source officielle

https://infoscience.epfl.ch/entities/publication/061f1224-b5f4-469d-a7ad-704b190b8256

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (27)

Concepts associés (32)

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.

Circuit complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes.

Succinct ordering and aggregation constraints in algebraic array theories

Viktor Kuncak, Rodrigo Raya

We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...

Elsevier Science Inc2024

Experimental and ab initio derivation of interface stress in nanomultilayered coatings: Application to immiscible Cu/W system with variable in-plane stress

Pandula Manura Liyanage, Claudia Cancellieri, Giacomo Lorenzin

Interface stress is a fundamental descriptor for interphase boundaries and is defined in strict relation to the interface energy. In nanomultilayers with their intrinsically high interface density, the functional properties are dictated by the interface st ...

Elsevier2024

Inhalation of Microplastics—A Toxicological Complexity

Florian Frédéric Vincent Breider, Myriam Borgatta

Humans are chronically exposed to airborne microplastics (MPs) by inhalation. Various types of polymer particles have been detected in lung samples, which could pose a threat to human health. Inhalation toxicological studies are crucial for assessing the e ...

2024