Lower bounds for some decision problems over C

DOI10.1016/S0304-3975(01)00273-0MaRDI QIDQ1605321zbMATHWikidataFDO

Authors Gregorio Malajovich

Publication date 15 July 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9904129

zbMATH Keywords

decision problems

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: Lower bounds for some explicit decision problems over the complex numbers are given.

Recommendations

• Lower bounds for linear decision lists
• scientific article; zbMATH DE number 1351079
• Publication:4886070
• scientific article; zbMATH DE number 4087011
• Lower bounds for covering problems
• Lowering Undecidability Bounds for Decision Questions in Matrices
• Decidability results for the boundedness problem
• Lower Bounds on Minimal Weight of Partial Reducts and Partial Decision Rules
• A lower bound on determinantal complexity
• A lower bound on determinantal complexity

Cites work

• scientific article; zbMATH DE number 1222560 (Why is no real title available?)
• scientific article; zbMATH DE number 611919 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On lower bounds for the complexity of polynomials and their multiples
• Polynomials with Rational Coefficients Which are Hard to Compute

Cited in

(2)

• Test complexity of generic polynomials
• Lower bounds and recursive methods for the problem of adjudicating conflicting claims

This page was built for publication: Lower bounds for some decision problems over \(C\)

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