Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Leela

Mädchen

  • "Leela" is female
  • "Leela" started this thread

Posts: 88

Date of registration: Sep 15th 2011

1

Wednesday, August 28th 2013, 3:37pm

KVA - Reduktionsschreibweise

Hallo!

Ich bin nun total durcheinander. :(
Vorweg: Gelesen als "A reduziert man auf B" bzw. "Wir können A über B entscheiden". Ist das soweit korrekt?

Beispiel: Ich möchte NP-Härte für Sprache A nachweisen und nutze das bekannte Problem B zur Reduktion.
Dann ist doch
Oder wird das genau umgekehrt geschrieben?

lg
Doro
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

2

Wednesday, August 28th 2013, 4:09pm

Quoted from "Leela"

Vorweg: Gelesen als "A reduziert man auf B" bzw. "Wir können A über B entscheiden". Ist das soweit korrekt?

Korrekt.

Quoted from "Leela"

Beispiel: Ich möchte NP-Härte für Sprache A nachweisen und nutze das bekannte Problem B zur Reduktion.
Dann ist doch
Oder wird das genau umgekehrt geschrieben?


Also. Um zu zeigen, dass A NP-hart ist benutzt Du ein Problem B von dem Du weißt, dass es NP-hart (oder meinetwegen auch NP-vollständig) ist und reduzierst dieses B *auf* A, also zeigst Du .

PS: Irgendwie zeigt der LaTeX Plugin den Quellcode für die Reduktionssymbole mit hoch P und tief m nicht richtig an, aber ich denke es ist klar wie es muss.
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Aug 28th 2013, 4:10pm)

  • Send private message

Leela

Mädchen

  • "Leela" is female
  • "Leela" started this thread

Posts: 88

Date of registration: Sep 15th 2011

3

Wednesday, August 28th 2013, 4:43pm

Ok. Also doch anders herum. Danke! :)
  • Send private message

Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

4

Wednesday, August 28th 2013, 7:52pm


Mit \textrm{$\leq$}^p_m kann man's sich hintricksen, aber vll. gehts auch noch einfacher ^^
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian
  • Send private message

Salz

Opa

  • "Salz" is male

Posts: 144

Date of registration: Dec 3rd 2009

5

Wednesday, August 28th 2013, 8:38pm

Mit \leq{}^P_m oder {\textstyle\leq^P_m} get es.
Damals…
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

6

Wednesday, August 28th 2013, 8:43pm

Hm richtig ist das aber auch nicht, weil dann das P und m in Bezug auf ein Leerzeichen gesetzt werden. D.h. um es visuell korrekt zu machen muss man da noch einen negativen Abstand mit \! setzen...
Das führt aber fälschlicherweise zu
"NP - The class of dashed hopes and idle dreams." Complexity Zoo
  • Send private message

Anselm

borlark

Posts: 164

Date of registration: Oct 13th 2010

Occupation: WiMi ThI

7

Wednesday, August 28th 2013, 9:01pm

Gerade mal auf Basis deiner Aussage rumprobiert:

mit \leq\!{}^P_m, also \! vor dem {}

Noch ne Alternative gefunden:

mit \leq\!\!\phantom{\leq}^P_m
Aber die ist nur wieder umständlicher ^^ Hatte \phantom irgendwie komfortabler in Erinnerung
"Once you figure out what a joke everything is, being the comedian's the only thing makes sense."
~The Comedian

This post has been edited 3 times, last edit by "Anselm" (Aug 28th 2013, 9:20pm)

  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

8

Wednesday, August 28th 2013, 9:23pm

Im Prinzip ist das irgendwie verbuggt, weil es ^ als overset und _ als underset interpretiert... Naja wie auch immer ;)

PS: ah es könnte auch sein, dass er die LaTeX Umgebung als abgesetzte Formel sieht, da wird nämlich ^ und _ immer als over/underset umgesetzt. Gibt es nen extra Befehl hier im Forum der einer Inline-Formel in LaTeX entspricht?
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Aug 28th 2013, 9:24pm)

  • Send private message

Salz

Opa

  • "Salz" is male

Posts: 144

Date of registration: Dec 3rd 2009

9

Wednesday, August 28th 2013, 9:59pm

Quoted from "Arne"

Gibt es nen extra Befehl hier im Forum der einer Inline-Formel in LaTeX entspricht?

mit \textstyle wird der Inline-Formel Stil gewählt, im gegensatz zum \displaystyle der offenbar auch für Formeln im Forum verwendet wird.

Ich muß mich aber selber korrigieren, korrekt ist die Verwendung von \nolimits, womit auch im displaymath-stye die Sub- und Superscripts hinter den jeweiligen Operator gesetzt werden: \leq\nolimits^P_m:
Damals…
  • Send private message

SammysHP

Forenwolf

  • "SammysHP" is male

Posts: 712

Date of registration: Oct 11th 2010

Location: Celle

Occupation: Informatiker

10

Thursday, August 29th 2013, 7:55am

Was ich schon immer mal wissen wollte: Ist das ein großes oder ein kleines P?

Was das LaTeX hier im Forum angeht, so sehe ich das als Bug, da nolimits bei einfachen Relationszeichen Standard sein sollte, während z.B. (im displaystyle) standardmäßig limits nutzt.
  • Send private message

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

11

Thursday, August 29th 2013, 8:16am

Ein großes P, weil es für die Klasse P wie Polynomialzeit steht. Andererseits ist es auch in gewissem Rahmen Definitions/Geschmackssache. Bei logspace-many-one Reduktionen kenne ich allerdings nur .
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

This post has been edited 1 times, last edit by "Arne" (Aug 29th 2013, 8:18am)

  • Send private message