**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Complexity class

Summary

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements. For instance, the class P is the set of decision problems solvable by a deterministic Turing machine in polynomial time. There are, however, many complexity classes defined in terms of other types of problems (e.g. counting problems and function problems) and using other models of computation (e.g. probabilistic Turing machines, interactive proof systems, Boolean circuits, and quantum computers).
The study of the relationships between complexity classes is a major ar

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related people

Related units

No results

No results

Related publications (14)

Loading

Loading

Loading

Related concepts (45)

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each ot

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the

P versus NP problem

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solve

Christoph Koch, Daniel Lupei, Val Tannen

In the context of incremental view maintenance (IVM), delta query derivation is an essential technique for speeding up the processing of large, dynamic datasets. The goal is to generate delta queries that, given a small change in the input, can update the materialized view more efficiently than via recomputation. In this work we propose the first solution for the efficient incrementalization of positive nested relational calculus (NRC+) on bags (with integer multiplicities). More precisely, we model the cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has a strictly lower cost than full re-evaluation. Then, we identify NRC+, a large fragment of NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that incremental maintenance for NRC+ is within the complexity class NC0 and we showcase how recursive IVM, a technique that has provided significant speedups over traditional IVM in the case of flat queries, can also be applied to IncNRC+.

Related courses (10)

Test of VLSI Systems covers theoretical knowledge related to the major algorithms used in VLSI test, and design for test techniques. Basic knowledge related to computer-aided design for test techniques, and their integration into a design-flow are presented.

D'une part, le cours aborde: (1) la notion d'algorithme et de représentation de l'information, (2) l'échantillonnage d'un signal et la compression de données et (3) des aspects
liés aux systèmes: ordinateur, mémoire, etc. D'autre part, le cours donne une introduction à la programmation.

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many domains.

Many map-reduce frameworks as well as NoSQL systems rely on collection programming as
their interface of choice due to its rich semantics along with an easily parallelizable set of
primitives. Unfortunately, the potential of collection programming is not entirely fulfilled
by current systems as they lack efficient incremental view maintenance (IVM) techniques
for queries producing large nested results. This comes as a consequence of the fact that
the nesting of collections does not enjoy the same algebraic properties underscoring the
optimization potential of typical collection processing constructs.
We propose the first solution for the efficient incrementalization of collection programming
in terms of its core constructs as captured by the positive nested relational calculus (NRC+)
on bags (with integer multiplicities). We take an approach based on delta query derivation,
whose goal is to generate delta queries which, given a small change in the input, can update
the materialized view more efficiently than via recomputation. More precisely, we model the
cost of NRC+ operators and classify queries as efficiently incrementalizable if their delta has
a strictly lower cost than full re-evaluation. Then, we identify IncNRC+, a large fragment of
NRC+ that is efficiently incrementalizable and we provide a semantics-preserving translation
that takes any NRC+ query to a collection of IncNRC+ queries. Furthermore, we prove that
incrementalmaintenance for NRC+ is within the complexity class NC0 and we showcase how
Recursive IVM, a technique that has provided significant speedups over traditional IVM in the
case of flat queries, can also be applied to IncNRC+ .
Existing systems are also limited wrt. the size of inner collections that they can effectively
handle before running into severe performance bottlenecks. In particular, in the face of nested
collections with skewed cardinalities developers typically have to undergo a painful process of
manual query re-writes in order to ensure that the largest inner collections in their workloads
are not impacted by these limitations.
To address these issues we developed SLeNDer, a compilation framework that given a nested
query generates a set of semantically equivalent (partially) shredded queries that can be
efficiently evaluated and incrementalized using state of the art techniques for handling skew
and applying delta changes, respectively. The derived queries expose nested collections to
the same opportunities for distributing their processing and incrementally updating their
contents as those enjoyed by top-level collections, leading on our benchmark to up to 16.8x
and 21.9x speedups in terms of offline and online processing, respectively.
In order to enable efficient IVM for the increasingly common case of collection programming
with functional values as in Links, we also discuss the efficient incrementalization of simplytyped
lambda calculi, under the constraint that their primitives are themselves efficiently
incrementalizable.

The human hand is an amazing tool, demonstrated by its incredible motor capability and remarkable sense of touch. To enable robots to work in a human-centric environment, it is desirable to endow robotic hands with human-like capabilities for grasping and object manipulation. However, due to its inherent complexity and inevitable model uncertainty, robotic grasping and manipulation remains a challenge. This thesis focuses on grasp adaptation in the face of model and sensing uncertainties: Given an object whose properties are not known with certainty (e.g., shape, weight and external perturbation), and a multifingered robotic hand, we aim at determining where to put the fingers and how the fingers should adaptively interact with the object using tactile sensing, in order to achieve either a stable grasp or a desired dynamic behaviour. A central idea in this thesis is the object-centric dynamics: namely, that we express all control constraints into an object-centric representation. This simplifies computa- tion and makes the control versatile to the type of hands. This is an essential feature that distinguishes our work from other robust grasping work in the literature, where generating a static stable grasp for a given hand is usually the primary goal. In this thesis, grasp adaptation is a dynamic process that flexibly adapts the grasp to fit some purpose from the objectâs perspective, in the presence of a variety of uncertainties and/or perturbations. When building a grasp adaptation for a given situation, there are two key problems that must be addressed: 1) the problem of choosing an initial grasp that is suitable for future adaptation, and more importantly 2) the problem of design- ing an adaptation strategy that can react adequately to achieve desired behaviour of the grasped object. To address challenge 1 (planning a grasp under shape uncertainty), we propose an approach to parameterizing the uncertainty in object shape using Gaussian Processes (GPs) and incorporate it as a constraint into contact-level grasp planning. To realize the planned contacts using different hands interchangeably, we further develop a prob- abilistic model to predict the feasible hand configurations, including hand pose and finger joints, given the desired contact points only. The model is built using the con- cept of Virtual Frame(VF), and it is independent from the choice of hand frame and object frame. The performance of the proposed approach is validated on two differ- ent robotic hands, an industrial gripper (4 DOF Barrett hand) and a humanoid hand (16 DOF Allegro hand) to manipulate objects of daily use with complex geometry and various texture (a spray bottle, a tea caddy, a jug and a bunny toy). In the second part of this thesis, we propose an approach to the design of adapta- tion strategy to ensure grasp stability in the presence of physical uncertainties of objects(object weight, friction at contacts and external perturbation). Based on an object-level impedance controller, we first design a grasp stability estimator in the object frame using the grasp experience and tactile sensing. Once a grasp is predicted to be unstable during online execution, the grasp adaptation strategy is triggered to improve the grasp stability, by either changing the stiffness at finger level or relocating the position of one fingertip to a better area.

Related lectures (10)