A Local Criterion for Polynomial-Time Stratified Computations

DOI10.1007/978-3-642-15331-0_8MaRDI QIDQ5747634zbMATH OpenOpenAlexFDO

Authors Luca Roversi, Luca Vercelli

Publication date 14 September 2010

Published in Foundational and Practical Aspects of Resource Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15331-0_8

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Structure of proofs (03F07) Complexity of proofs (03F20) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Polynomial-time computation via local inference relations
• A POLYNOMIAL TIME ALGORITHM FOR LOCAL TESTABILITY AND ITS LEVEL
• New techniques and tighter bounds for local computation algorithms
• Local search and the local structure of NP-complete problems
• On the probe complexity of local computation algorithms
• On the locality of some NP-complete problems
• scientific article; zbMATH DE number 1948176
• Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
• scientific article; zbMATH DE number 1884459

Cited in

(5)

• Paths-based criteria and application to linear logic subsystems characterizing polynomial time
• A type-assignment of linear erasure and duplication
• Some Complexity and Expressiveness Results on Multimodal and Stratified Proof Nets
• Polynomial-time computation via local inference relations
• Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic

This page was built for publication: A Local Criterion for Polynomial-Time Stratified Computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5747634)