Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Inapproximability results for equations over finite groups
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 312, no 1, 17-45 p.Article in journal (Refereed) Published
Abstract [en]

An equation over a finite group G is an expression of form w(1)w(2). . .w(k) = 1(G), where each w(i) is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the equality is realized. We study the problem of simultaneously satisfying a family of equations over a finite group G and show that it is NP-hard to approximate the number of simultaneously satisfiable equations to within \G\ - epsilon for any epsilon > 0. This generalizes results of Hastad (J. ACM 48 (4) (2001) 798), who established similar bounds under the added condition that the group G is Abelian.

Place, publisher, year, edition, pages
2004. Vol. 312, no 1, 17-45 p.
Keyword [en]
optimization, approximation, groups, finite groups, probabilistically checkable proofs, NP-hardness
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-43803DOI: 10.1016/S0304-3975(03)00401-8ISI: 000188530600003Scopus ID: 2-s2.0-0347024174OAI: oai:DiVA.org:kth-43803DiVA: diva2:448985
Note
QC 20111019Available from: 2011-10-19 Created: 2011-10-18 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Engebretsen, LarsHolmerin, Jonas
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Theoretical Computer Science
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf