scientific article; zbMATH DE number 7168145
From MaRDI portal
Publication:5216300
zbMath1442.68061arXiv1805.02724MaRDI QIDQ5216300
Martín Muñoz, Cristian Riveros, Marcelo Arenas
Publication date: 17 February 2020
Full work available at URL: https://arxiv.org/abs/1805.02724
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The consequences of eliminating NP solutions
- The complexity of computing the permanent
- Elements of finite model theory.
- Handbook of weighted automata
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- The complexity of optimization problems
- Optimization, approximation, and complexity classes
- Gap-definable counting classes
- Logical definability of NP optimization problems
- Counting quantifiers, successor relations, and logarithmic space
- Metafinite model theory
- Logical definability of counting functions
- Descriptive complexity of \(\#\)P functions
- A complexity theory for feasible closure properties
- Weighted automata and weighted logics
- Subtractive reductions and complete problems for counting complexity classes
- Enumeration Complexity of Logical Query Problems with Second-order Variables
- Polynomial Space Counting Problems
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- On Counting Independent Sets in Sparse Graphs
- Relational queries computable in polynomial time
- Nondeterministic Space is Closed under Complementation
- The Complexity of Enumeration and Reliability Problems
- Monadic generalized spectra
- Computational Complexity of Probabilistic Turing Machines
- Making Nondeterminism Unambiguous
- Descriptive Complexity of #AC^0 Functions
- Computational Complexity
- The Complexity of Counting Functions with Easy Decision Version
- The complexity theory companion
This page was built for publication:
