SpringerLink
Log in

Trial and Error Algorithms

  • Living reference work entry
  • First Online:
Encyclopedia of Algorithms

  • 397 Accesses

Years and Authors of Summarized Original Work

  • 2013(1); Bei, Chen, Zhang

  • 2013(2); Bei, Chen, Zhang

Problem Definition

This problem investigates the effect of the lack of input information on computational hardness. The central question under investigation is the following:

How much extra difficulty is introduced due to the lack of input knowledge?

We explore this question by studying search problems. Suppose that on an input instance x, there is a set S(x) of solutions. A search problem is to find a solution s ∈ S(x) for the input x. More specifically, we consider the fairly broad class of Constraint Satisfaction Problems (CSPs): Suppose that there is an input space {0, 1}n and a space Ω = { 0, 1}m of candidate solutions. The problem is defined by a number of constraints C 1, C 2, …, C m (, …), where each \(C_{i} :\{ 0,1\}^{n+m} \rightarrow \{ 0,1\}\) is a 0-1 function on the input and solution variables. The valid solutions for input x are defined as those sthat satisfy all...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Recommended Reading

  1. Angluin D (2004) Queries revisited. Theor Comput Sci 313(2):175–194

    Article  MathSciNet  Google Scholar 

  2. Balcan M, Blum A (2010) A discriminative model for semi-supervised learning. JACM 57(3):19

    Article  MathSciNet  Google Scholar 

  3. Barto A, Sutton R (1998) Reinforcement learning: an introduction. MIT, Cambridge

    Google Scholar 

  4. Bei X, Chen N, Zhang S (2013) On the complexity of trial and error. In: Proceedings of the forty-fifth annual ACM symposium on theory of computing. ACM, New York, pp 31–40

    Google Scholar 

  5. Bei X, Chen N, Zhang S (2013) Solving linear programming with constraints unknown. ar**v:1304.1247

    Google Scholar 

  6. Chen X, Deng X, Teng S (2009) Settling the complexity of computing two-player nash equilibria. JACM 56(3):14

    Article  MathSciNet  Google Scholar 

  7. Daskalakis C, Goldberg P, Papadimitriou C (2009) Computing a nash equilibrium is PPAD-complete. SIAM J Comput 39(1):195–259

    Article  MATH  MathSciNet  Google Scholar 

  8. Grotschel M, Lovasz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer, Berlin/New York

    Book  Google Scholar 

  9. Ivanyos G, Kulkarni R, Qiao Y, Santha M, Sundaram A (2014) On the complexity of trial and error for constraint satisfaction problems. In: Automata, languages, and programming. Lecture notes in computer science, vol 8572. Springer, Berlin/Heidelberg, pp 663–675

    Google Scholar 

  10. Nisan N, Roughgarden T, Tardos E, Vazirani V (2007) Algorithmic game theory. Cambridge University Press, Cambridge/New York

    Book  Google Scholar 

  11. Roth A (2008) Deferred acceptance algorithms: history, theory, practice, and open questions. Int J Game Theory 36:537–569

    Article  Google Scholar 

  12. Roth A, Sotomayor M (1992) Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, Cambridge/New York

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore

    **aohui Bei

  2. Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore

    Ning Chen

  3. The Chinese University of Hong Kong, Hong Kong, China

    Shengyu Zhang

Authors
  1. **aohui Bei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ning Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shengyu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to **aohui Bei .

Editor information

Editors and Affiliations

  1. Dept. Electrical Engineering & Computer Science, Northwestern University, Evanston, Illinois, USA

    Ming-Yang Kao

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer Science+Business Media New York

About this entry

Cite this entry

Bei, X., Chen, N., Zhang, S. (2015). Trial and Error Algorithms. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-27848-8_789-1

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-27848-8_789-1

  • Received:

  • Accepted:

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Online ISBN: 978-3-642-27848-8

  • eBook Packages: Springer Reference Computer SciencesReference Module Computer Science and Engineering

Publish with us

Policies and ethics

Search

Navigation