On Exact and Approximate Solutions for Hard Problems: An Alternative Look

R. S. Bartholo, C. A. Cosenza, F. A. Doria, M. Doria and A. Teixeira

No 1103, ASSRU Discussion Papers from ASSRU - Algorithmic Social Science Research Unit

Abstract: We discuss in an informal, general audience style the da Costa-Doria conjecture about the independence of the P = NP hypothesis and try to briefly assess its impact on practical situations in economics. The paper concludes with a discussion of the Coppe-Cosenza procedure, which is an approximate, partly heuristic algorithm for allocation problems.

Keywords: P vs. NP; allocation problem; assignment problem; traveling salesman; exact solution for NP problems; approximate solutions for NP problems; undecidability; incompleteness (search for similar items in EconPapers)
Date: 2011
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.assru.economia.unitn.it/files/DP_03_2011.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to www.assru.economia.unitn.it:80 (No such host is known. )

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:trn:utwpas:1103

Access Statistics for this paper

More papers in ASSRU Discussion Papers from ASSRU - Algorithmic Social Science Research Unit Contact information at EDIRC.
Bibliographic data for series maintained by assru.tm@gmail.com (assru.tm@gmail.com).