Gibt es Probleme, die mit zunehmender Größe einfacher werden?

62

Dies mag eine lächerliche Frage sein, aber ist es möglich, dass ein Problem auftritt, das mit zunehmender Größe der Eingaben tatsächlich einfacher wird? Ich bezweifle, dass solche praktischen Probleme vorliegen, aber vielleicht können wir ein entartetes Problem erfinden, das diese Eigenschaft hat. Vielleicht beginnt es sich zu "lösen", wenn es größer wird, oder es verhält sich auf eine andere bizarre Art und Weise.

dsaxton
quelle
7
Ein echtes Problem mit dieser Eigenschaft, das mir in den Sinn kommt, ist das Knacken von ungesalzenem Passwort-Hash, wenn es wie folgt formuliert ist: "Bei n Hashes muss mindestens ein Hash geknackt werden." Da die Rissgeschwindigkeit linear mit n skaliert, ist die Laufzeit proportional zu 1 / n - mit der Ausnahme, dass wir keine definitive Zeit zuweisen können, da die Rissbildung stochastisch ist und keine konstante Obergrenze für die Zeit aufweist.
Am
1
@amon Die Laufzeit skaliert nicht wie . Es braucht Zeit , um die Hashes zu lesen, die Sie als Eingabe erhalten haben! n n1/nnn
David Richerby
3
Meinen Sie es absolut oder relativ einfacher? Welche Kostenmaßnahmen erlauben Sie? Benötigen Sie streng sinkende Kosten oder ist eine Nichterhöhung (ab einem gewissen Punkt) ausreichend?
Raphael
2
@DavidRicherby In diesem Beispiel ist es legitim, die Kosten für das Lesen der Eingabe zu ignorieren, solange ich keine Aussage über die absoluten Kosten mache. Stattdessen steigt die Geschwindigkeit linear mit dem Eingang. Daher ist n · T (1)> T (n), auch wenn die Kosten für das Lesen der Eingabe berücksichtigt werden. Dh für dieses Problem ist es einfacher, eine große Eingabe auf einmal zu lösen, als die Eingabe aufzuteilen, obwohl das Problem teilbar ist. Ich sage nicht, dass T (n)> T (n + 1) für alle n.
amon
4
An alle, die noch eine Antwort des Formulars posten möchten: "Ein Problem, bei dem die Eingabe eine Frage plus ein paar Hinweise zur Antwort ist": Dies funktioniert nicht. Die schwierigsten Eingaben der Länge sind diejenigen, bei denen Sie alle Bits verwenden, um die Frage zu stellen und keine Hinweise zu geben. Die Tatsache, dass es einfach ist, kurze Fragen mit vielen Hinweisen zu beantworten, bedeutet nicht, dass die Laufzeit im ungünstigsten Fall gut ist. nnn
David Richerby

Antworten:

39

Nein, es ist nicht möglich, zumindest nicht im asymptotischen Sinne, wo Sie das Problem haben müssen, immer einfacher zu werden, als es .n

Sei die bestmögliche Laufzeit zur Lösung eines solchen Problems, wobei die Größe der Eingabe ist. Beachten Sie, dass die Laufzeit ein Zähler für die Anzahl der Anweisungen ist, die vom Algorithmus ausgeführt werden. Es muss sich also um eine nicht negative Ganzzahl handeln. Mit anderen Worten, für alle . Wenn wir nun eine Funktion , sehen wir, dass es keine solche Funktion gibt, die streng monoton abnimmt. (Was auch immer ist, es muss endlich sein, sagen wir ; aber da monoton streng abnimmt, ist undn T ( n ) N n T : NN T ( 0 ) T ( 0 ) = c T T ( c ) 0 T ( c + 1 ) - 1 T ( n ) n 0 n n 0 T ( n )T(n)nT(n)NnT:NNT(0)T(0)=cTT(c)0T(c+1)1, was unmöglich ist.) Aus ähnlichen Gründen gibt es keine asymptotisch streng abnehmende Funktion: Ebenso können wir beweisen, dass es keine Laufzeitfunktion gibt, in der existiert, so dass für alle , ist monoton streng abnehmend (jede solche Funktion müsste irgendwann negativ werden).T(n)n0nn0T(n)

Ein solches Problem kann also nicht existieren, aus dem einfachen Grund, dass Laufzeiten nicht negative ganze Zahlen sein müssen.


Beachten Sie, dass diese Antwort nur deterministische Algorithmen abdeckt (dh Worst-Case-Laufzeit). Es schließt die Möglichkeit randomisierter Algorithmen nicht aus, deren erwartete Laufzeit für immer streng monoton abnimmt. Ich weiß nicht, ob es einen solchen Algorithmus geben kann. Ich danke Beni Cherniavsky-Paskin für diese Beobachtung .

DW
quelle
9
Dies ist ein schöner Beweis, aber ich bin mit der Prämisse nicht einverstanden. Anstatt nach einer streng monoton abnehmenden Laufzeit zu fragen, könnte die Frage vernünftigerweise eine Funktion erfordern, bei der ein a, b mit a <b existiert, so dass T (a)> T (b), dh es ist nicht streng monoton abnehmend. Dann ist es natürlich möglich, geeignete ganzzahlige Funktionen zu finden. Aber warum ganze Zahlen? Ich hatte den Eindruck, dass die Laufzeit eine Zeit angibt, keine Befehlsanzahl (außer natürlich für Turing-Maschinen), und dass der T-Ausdruck die nicht ganzzahligen Operationen wie log () oder nicht ganzzahlige Exponenten verwenden kann.
Am
2
@amon "Laufzeit bezeichnet eine Zeit, keine Befehlsanzahl" Absolut nicht. Die Laufzeit ist immer eine Anweisungsanzahl. Alles andere wäre unmöglich zu überlegen, da es von unendlich vielen Implementierungsdetails abhängen würde.
David Richerby
3
So vage die Frage auch ist, ich verstehe nicht, wie sie eine Kostenfunktion von beispielsweise . Nun, aber für "small" , so dass das Problem relativ gesehen "einfacher" wird. (Die absoluten Kosten steigen natürlich asymptotisch). T ( n ) n T ( n ) n 2 nT(n)=n2(1+ϵ)n+nT(n)nT(n)n2n
Raphael
2
@Raphael, ist kein Problem, das leichter wird: wird größer, wenn größer wird, und das Problem wird schwieriger, wenn größer wird, sobald groß genug ist. Ich habe im ersten Satz meiner Antwort festgestellt, dass kein Problem für immer einfacher werden kann. Natürlich kann ein Problem für eine Weile einfacher werden ( kann beispielsweise für abnehmen ), aber es kann nicht für immer einfacher werden. T ( n ) n n n T ( n ) , n cT(n)nT(n)nnnT(n)nc
DW
1
Selbst bei ganzzahligen Zeiten kann für einen randomisierten Algorithmus die erwartete Zeit (oder ein anderes Maß für die Verteilung) ein Bruchteil sein und sich allmählich einer Konstante von oben annähern. [Dies bedeutet nicht, dass solche Probleme tatsächlich existieren, nur dass das Argument "keine solche Funktion existiert" nicht ausreicht.]T
Beni Cherniavsky-Paskin
25

Obwohl es nicht ganz die Antwort auf Ihre Frage, der Boyer-Moore-Algorithmus kommt in der Nähe. Wie Robert Moore auf seiner Webseite über den Algorithmus sagt,

Unser Algorithmus hat die eigentümliche Eigenschaft, dass der Algorithmus umso schneller arbeitet, je länger das Muster ist.

Mit anderen Worten, im Allgemeinen sucht der Algorithmus nach einer Instanz einer Zielzeichenfolge in einer Quellzeichenfolge und nach einer festen Quellzeichenfolge. Je länger die Zielzeichenfolge ist, desto schneller wird der Algorithmus ausgeführt.

Rick Decker
quelle
10
Vermutlich ist das Muster nicht die Größe des Problems, sondern die Länge der zu durchsuchenden Zeichenfolge. Wie in der obigen Bemerkung von David Richerby würde ich argumentieren, dass die Länge des Musters eher ein Hinweis darauf ist, wie das Problem zu lösen ist (es geht darum, die Zeichenfolge zu durchsuchen), als das Problem selbst (zu sehen, ob ein Muster mit einer Zeichenfolge einer bestimmten Länge übereinstimmt) .)
Kevin
4
@ Kevin Die Anweisung schlägt vor, dass das Suchen eines Musters mit der Länge in einem Text mit der Länge schneller ist als das Suchen eines Musters mit der Länge . Wenn ich mir solche Eingaben mit festen Beziehungen (dh Paare von Zeichenfolgen) anschaue, hat Rick meiner Meinung nach die Frage angemessen beantwortet (wenn nicht im klassischen, asymptotischen Sinne). nlognnnlogn
Raphael
10

Aus rein mathematischer, rein CS-Algorithmus-Sicht ist dies natürlich unmöglich. Tatsächlich gibt es jedoch mehrere Beispiele aus der Praxis, anhand derer das Skalieren Ihres Projekts vereinfacht wird. Viele davon sind für Endbenutzer nicht intuitiv.

Richtungen : Je länger Ihre Richtungen werden, desto einfacher werden sie manchmal. Wenn ich zum Beispiel möchte, dass Google Maps mir eine Wegbeschreibung für 3000 Meilen in Richtung Westen gibt, könnte ich an die Westküste fahren - und dort Anweisungen für Geländefahrten erhalten. Aber wenn ich 6000 Meilen westlich fahren wollte, hätte ich am Ende wesentlich einfachere Anweisungen: Steigen Sie in ein Flugzeug von NYC nach Hokkaido. Es ist algorithmisch ziemlich schwierig, mir eine Cross-Country-Route zu geben, die Verkehr, Straßen, Wetter usw. enthält, aber es ist vergleichsweise viel einfacher, mich in ein Flugzeug zu setzen und Flüge in einer Datenbank nachzuschlagen. ASCII-Graph von Schwierigkeitsgrad gegen Distanz:

           |     /
           |    /
Difficulty |   /                  ____-------
           |  /           ____----
           | /    ____----
            ---------------------------------
                       Distance

Rendern : Angenommen, ich möchte ein Gesicht und 1000 Gesichter rendern. Dies gilt für eine Plakatwerbung, sodass beide endgültigen Bilder 10000 x 5000 Pixel groß sein müssen. Ein Gesicht realistisch zu rendern wäre schwierig - bei einer Auflösung von mehreren tausend Pixeln muss man wirklich leistungsstarke Maschinen verwenden -, aber für die Menge von 1000 Gesichtern muss jedes Gesicht nur zehn Pixel breit sein und kann einfach geklont werden! Ich könnte wahrscheinlich 1000 Gesichter auf meinem Laptop rendern, aber ein realistisches Gesicht mit einer Auflösung von 10000px zu rendern würde sehr lange dauern und leistungsstarke Maschinen benötigen. ASCII-Diagramm der Schwierigkeit im Vergleich zu gerenderten Objekten, das zeigt, wie die Schwierigkeit beim Rendern von n Objekten zu einem Bild einer festgelegten Größe schnell abnimmt und dann langsam zurückkehrt:

           | -    
           |- -                     _________
Difficulty |   --      ______-------            
           |     ------      
           |       
            ---------------------------------
                        Objects

Hardware-Kontrolle : Viele Dinge mit Hardware werden viel einfacher. "Motor um 1 Grad bewegen" ist schwierig und / oder unmöglich, und Sie müssen sich mit allen möglichen Dingen auseinandersetzen, die Sie für "Motor um 322 Grad bewegen" nicht hätten erledigen müssen.

Aufgaben von kurzer Dauer: Angenommen, Sie möchten, dass Gegenstand X jede Sekunde (für sehr wenig Zeit) eingeschaltet ist. Wenn Sie die Laufzeit von X erhöhen, benötigen Sie weniger komplexe Software und Hardware.

Owen Versteeg
quelle
Geben Sie in Ihrem Beispiel "Richtungen" genau an, was das Rechenproblem und was die Instanz ist. Es ist mir überhaupt nicht klar, dass Ihr Beispiel für 6 km eine größere Instanz oder nur ein Beispiel für einen einfachen Teil von etwas ist (z. B. wenn ich Ihnen einen großen Graphen mit verbundenem Graphen plus einem isolierten Scheitelpunkt gebe, der nach kürzesten Wegen fragt, ist dies im Allgemeinen "schwierig", aber es ist trivial, nach einem kürzesten Weg vom isolierten Scheitelpunkt zu fragen. Was ist für Ihr Rendering-Beispiel das eigentliche Rechenproblem? An welcher Instanz messen Sie die Komplexität?
David Richerby
Das Rendering-Beispiel scheint nicht dasselbe Problem zu haben: Das erste ist das Rendern eines einzelnen Bildes. Die zweite Methode rendert viele kleine Bilder und fügt dann mehrere Kopien dieser Bilder in einen bestimmten Bereich ein.
David Richerby
Ich denke, um die Parameter zu reisen, wäre der Name der 2 Städte und n wäre die Anzahl der Zeichen, um sie zu codieren.
Emory
3

Es gibt Fälle. Dies sind die Fälle, in denen das Erfolgskriterium von den Daten abhängt, anstatt eine einzige Antwort zu finden. Beispielsweise können statistische Prozesse, deren Ergebnisse mit Konfidenzintervallen formuliert sind, einfacher werden.

Ein besonderer Fall, an den ich denke, sind Probleme, die einen Übergang von diskretem Verhalten zu kontinuierlichem Verhalten aufweisen, wie z. B. Flüssigkeitsflüsse. Das Lösen des kleinen Problems innerhalb eines gewissen Fehlergrades kann das Modellieren aller diskreten Wechselwirkungen umfassen, was möglicherweise einen Supercomputer erforderlich macht. Das kontinuierliche Verhalten ermöglicht häufig Vereinfachungen, ohne dass Ergebnisse außerhalb einer damit verbundenen Fehlergrenze erzielt werden.

Cort Ammon
quelle
2

Die Frage ist interessant und NÜTZLICH, denn unsere Philosophie in der Informatik ist es, Probleme zu lösen, je mehr wir lesen, desto schwieriger wird es. Tatsächlich können die meisten der Probleme, die auf typische (schwierige) Art und Weise dargestellt werden, auf einfache Weise dargestellt werden. selbst wenn man die Antwort von DW kennt (was falsch ist, wenn man bedenkt, dass einfach nicht schneller bedeutet, bedeutet "weniger langsam"; man muss also keine negativen Zeiten finden, man muss asymptotische Zeiten finden).

Der Trick, einen zu finden, besteht darin, den Teil der Lösung wie Hinweise als Eintrag zu setzen und den Eintrag des Problems als konstanten Parameter zu betrachten.

Beispiel: Was ist der längste Weg im Auto zwischen London und Paris, um zu vermeiden, zweimal eine französische und eine britische Stadt zu besuchen und kein anderes Land zu besuchen? Überlegen Sie, Sie müssen nach Birmingham vor Ashford, Orleans vor Versailles, La Rochelle vor Limoge usw. gehen.

Es ist klar, dass dieses Problem bei langen Einträgen einfacher ist als bei kurzen.

Anwendungsbeispiel: Stellen Sie sich ein Spiel vor, das von der Maschine verwaltet wird, und das IA des Computers muss bestimmen, ob er mehr im Spiel erforschen muss, um weitere Hinweise zu finden, oder ob es jetzt an der Zeit ist, die beste Entscheidung zu treffen .

Juan Manuel Dato
quelle
2
Ihr Beispiel funktioniert nicht. Instanzen, die groß sind, weil sie so viele Hinweise haben, dass die Hinweise eine lineare Reihenfolge der Scheitelpunkte des Diagramms bestimmen, sind in der Tat einfach. Instanzen, die groß sind, weil sie einen großen Graphen mit fast keinen Hinweisen ergeben, sind jedoch genauso schwierig wie das gewöhnliche Hamilton-Pfadproblem. Daher wird die Laufzeit im schlechtesten Fall eines Algorithmus, der dieses Problem löst, mindestens so schlecht sein wie die Laufzeit im schlechtesten Fall des besten Algorithmus für den Hamilton-Pfad, der nicht "superleicht" zu sein scheint.
David Richerby
@ David, deine Antwort ist völlig falsch: 1. Der Eintrag ist kein Diagramm: Das große Diagramm ist ein PARAMETER. Das Hamilton-Problem wird also in eine Konstante umgewandelt (sehr groß, aber eine Konstante). 2. Der Eintrag ist die Lösung des Problems. Wenn er größer ist, bieten Sie eine kombinatorische Explosion von Hinweisen an. Ein Eintrag von einem Hinweis gibt eine Hilfe, zwei Hinweise das Doppelte, drei Hinweise liegen in der Nähe von vier Zweimal ..., weil Sie mögliche Lösungen ausschließen. Das war also kein Hamiltonianer, das ist eine Lösung aus einem bestimmten Diagramm und das Problem ist, WAS mit Teilen der Lösungen zu tun hat.
Juan Manuel Dato
Ich denke, Ihr Argument ist interessant, da größere Instanzen in gewissem Sinne "einfacher" sind, aber ich denke, die Antwort auf die ursprüngliche Frage lautet letztendlich "nein". Da der Graph endlich ist, gibt es also nur endlich viele mögliche Hinweise. Daher kann jede Instanz in konstanter Zeit gelöst werden (z. B. mithilfe einer Nachschlagetabelle). Auch wenn größere Instanzen in der (asymptotischen) Informatik (intuitiv) einfacher sind, sind alle Instanzen gleich schwer (in konstanter Zeit lösbar).
Tom van der Zanden
@ Tom, ich bin damit einverstanden, dass Ihre Überlegung bezüglich der Komplexität konstant bleibt, aber das Problem ist, wie wir die neuen Hinweise akzeptieren: Wenn mit unserer Philosophie der Berechnung des langen Eintrags nicht besser als ein kurzer Eintrag ist, müssen wir unsere Philosophie ändern - weil das eine Tatsache ist: lange Einträge bedeuten einfachere Probleme. So können wir nicht arbeiten ... Ich würde mein Buch empfehlen, aber ich habe keinen Ruf ...
Juan Manuel Dato
nlogn
1

Stellen Sie sich ein Programm vor, das das eingibt, was Sie über ein Kennwort wissen, und dann versucht, es zu knacken. Ich denke das macht was du willst. Zum Beispiel:

  • Keine Eingabe-> Brute-Force-Riss über alle Symbole und ein Wort beliebiger Länge
  • Länge des Passworts -> Brute erzwinge alle Symbole in einem Wort dieser Länge
  • Enthaltene Symbole -> Verkleinert die Liste der zu überprüfenden Symbole
  • ...
  • Enthaltene Symbole mit mehreren Vorkommen und Längen -> Berechnen Sie nur Permutationen
  • Alle Symbole in richtiger Reihenfolge -> lösten sich grundsätzlich von selbst

Ich sollte hinzufügen, dass dies ein Trick ist, da das Problem umgekehrt zur Eingabegröße ist. Sie können eine Abstraktionsebene weglassen und sagen, dass die Eingabegröße für keine Eingabe groß (alle Symbole und Wortlängen prüfen) und klein ist, wenn Sie am Anfang das richtige Kennwort eingeben.

Es kommt also darauf an, wie viel Abstraktion Sie zulassen.

RunOrVeith
quelle
2
b
0

Tatsächlich habe ich ein Problem, das mit zunehmenden Datenmengen kleiner wird. Eine meiner Anwendungen zeichnet Attribute eines bestimmten Produkts auf, beispielsweise Käse. Attribute sind zum Beispiel CheeseType, Brand, Country, Area, MilkType usw. Jeden Monat oder so erhalte ich eine Liste der neuen Käsesorten, die während dieser Zeit auf den Markt kamen, zusammen mit ihren Attributen. Diese Attribute werden nun von einer Gruppe von Menschen von Hand eingegeben. Einige machen Tippfehler oder kennen den Wert nicht für alle Attribute.

Wenn Sie in meiner Datenbank suchen, versuche ich anhand von Statistiken vorherzusagen, wie der Käse schmeckt, basierend auf diesen Attributen. Was passiert, ist, dass ich für jedes Attribut eine Reihe von Werten erhalte; Einige sind gültig, andere sind ungültig. Das Beseitigen oder Korrigieren dieser ungültigen ist nur möglich, wenn ich genügend Daten habe. Es geht darum, den Unterschied zwischen echten Werten und Rauschen zu machen, ohne seltene, aber gültige Werte zu eliminieren.

Wie Sie sich vorstellen können, ist bei geringer Lautstärke das Rauschen zu wichtig, um die Probleme richtig zu beheben. Wenn Sie 5 Instanzen von Cheddar, 1 von Brie, 1 von Bri und 1 von Chedar haben, wie kann ich feststellen, welche richtig und welche ein Tippfehler ist? Mit zunehmender Lautstärke bleiben die Tippfehler in der Regel sehr niedrig, aber die seltenen Werte werden in einigen entscheidenden Schritten erhöht, sodass sie dem Rauschen entkommen (gestützt auf die Erfahrung). In diesem Fall könnte ich mir zum Beispiel 50000 Cheddar, 3000 Brie, 5 Bri, 15 Chedar vorstellen.

Also ja, einige Probleme lösen sich schließlich von selbst, wenn Sie über genügend Daten verfügen.

chris
quelle
1
Dies schlägt aus dem üblichen Grund fehl. Eine große Eingabe könnte eine sein, in der die Leute Ihnen von vielen verschiedenen Käsesorten erzählen, und nicht eine, in der sie Ihnen von einigen Käsesorten erzählen, von denen einige sie falsch buchstabieren. Es ist auch nicht klar, dass "einfacher" als "Ermöglichen eines höheren Vertrauens in das Ergebnis" interpretiert werden soll.
David Richerby
Dies ist ein echtes Problem (ich hatte es schon zweimal), das mit einer geringen Datenmenge nicht gelöst werden kann. Es kann gute Werte von falschen unterscheiden, und es wird sogar einfacher, diese zu unterscheiden, wenn die Lautstärke hoch wird. Es hat den Vorzug, die Frage zu beantworten: "Gibt es Probleme, die mit zunehmender Größe einfacher werden?" Es spielt keine Rolle, wie viele Käsesorten auftauchen, schließlich werden sie mit genügend Volumen mehr "Treffer" haben als Tippfehler. Das ist cs .stackexchange, nicht Mathe, also sind die Probleme unterschiedlich, und manchmal geht es einfach darum, mehr Vertrauen in die Ergebnisse zu haben.
Chris
Ist das nicht auch die Prämisse der TV-Show Numbers ? Oder zumindest einige Episoden - ich erinnere mich an eine Szene, in der der Mathematiker bemerkt, dass der Algorithmus, den er zur Lösung des vorliegenden Problems verwendet, mit einem größeren Datensatz effektiver wird.
Dan Henderson
2
"Wird effektiver"! = "Wird einfacher".
David Richerby
-1

Betrachten Sie das NP-vollständige Problem 3-SAT. Wenn Sie das Problem weiterhin durch Eingabe der Form x_i = true / false vergrößern, konvertieren Sie die einzelnen Disjunktionen entweder in Klauseln mit zwei Variablen, wodurch ein 2-SAT-Problem entsteht, das eindeutig P ist, oder Sie erhalten einfach das Ergebnis eine wahr / falsch Antwort.

Für den Fall, dass die x_i = true / false-Eingänge redundant sind (häufig bereitgestellte gleiche Eingänge oder widersprüchliche Eingänge), können Sie die Eingänge einfach sortieren und entweder die redundanten Werte ignorieren oder einen Fehler melden, wenn die Werte widersprechen.

Ich denke auf jeden Fall, dass dies ein „realistisches“ Problem darstellt, das mit zunehmender Anzahl von Eingaben leichter zu lösen ist. Der einfachere Aspekt besteht darin, ein NP-vollständiges Problem in ein P-Problem umzuwandeln. Sie können das System trotzdem spielen, indem Sie lächerliche Eingaben machen, so dass nur das Sortieren länger dauern würde, als es das Problem brutal erzwingen würde.

Ein wirklich cooles Szenario wäre, wenn wir bereit wären, T (0) zu akzeptieren (unter Verwendung der DW-Notation in der obigen Antwort), dass es unendlich sein kann. Zum Beispiel könnte T (0) gleichbedeutend mit dem Lösen des Halteproblems von Turing sein. Wenn wir uns ein Problem ausdenken könnten, das durch Hinzufügen weiterer Eingaben in ein lösbares Problem umgewandelt wird, haben wir Gold getroffen. Beachten Sie, dass es nicht ausreicht, es asymptotisch in ein lösbares Problem umzuwandeln - denn das ist genauso schlimm wie brachiales Erzwingen des Problems.

v vv cvvcv
quelle
1
Diese speziellen Eingaben werden einfacher. Wenn Sie jedoch alle möglichen Eingaben berücksichtigen, wird 3SAT im Allgemeinen erheblich schwieriger, wenn Sie mehr Klauseln hinzufügen: Die harten Eingaben sind diejenigen ohne diese "Hinweis" -Klauseln. Wenn Sie allgemeine Eingaben nicht zulassen, müssen Sie genau angeben, welche Eingaben Sie zulassen.
David Richerby
Zunächst einmal: Wir sind uns einig, dass das Hinzufügen weiterer Eingaben die Laufzeit verlängern kann. Ich sage im Wesentlichen dasselbe wie oben. Zweitens sage ich klar, dass wir ein bestehendes 3-SAT nehmen und nur Eingaben der Form x_i = true / false hinzufügen. Ich denke, das ist klar genug, und ich muss keine weiteren Erklärungen abgeben. Ich denke, Sie nehmen sich die Mühe, die am meisten missverstandene Interpretation von dem zu bilden, was ich geschrieben habe. Bitte mach dir keine Sorgen.
v vv cvvcv
1
Nein im Ernst. Welches Rechenproblem lösen Sie? Ein Computerproblem besteht darin, die Zugehörigkeit zu einer Reihe von Zeichenfolgen zu bestimmen (sagen wir eine Reihe von Formeln, um Probleme mit der Codierung zu vermeiden). Was ist die Menge von Formeln, für die Sie behaupten, dass es einfacher ist, zu entscheiden, ob sich eine lange Formel in der Menge befindet, als zu entscheiden, ob sich eine kurze Formel in der Menge befindet? Sobald Sie versuchen, dies zu präzisieren, bin ich mir ziemlich sicher, dass Ihre Behauptung auseinanderfallen wird.
David Richerby
Können Sie bitte Ihr Verständnis von "meinem Anspruch" deutlich machen? Ich bin mir ziemlich sicher, dass Sie mit der Verschwendung von Internetbandbreite aufhören werden, sobald Sie versuchen, dies zu präzisieren.
v vv cvvcv
Ich bin ein Informatiker, kein Gedankenleser. Deinen Anspruch genau zu formulieren ist deine Aufgabe, nicht meine.
David Richerby
-1

Die Frage lautet: "Ist es möglich, ein Problem zu haben, das mit zunehmender Größe der Eingaben tatsächlich einfacher wird?" Was ist, wenn die Eingaben Ressourcen sind , die vom Algorithmus für die Arbeit an einem Job verwendet werden. Es ist allgemein bekannt, dass je mehr Ressourcen desto besser sind. Unten sehen Sie ein Beispiel, in dem es umso besser ist, je mehr Mitarbeiter vorhanden sind.


n
tp


n

3) Ausgabe:
Die Ausgabe gibt die Pfade zwischen den Aufgaben an, die von den Mitarbeitern ausgeführt werden müssen. Jeder Pfad ist mit der Anzahl der Mitarbeiter verknüpft, die ihn verwenden. Zum Beispiel:

n1
n2
n3
n4
n5

4) Mögliche Lösung:
Eine mögliche Lösung besteht darin, zuerst den kürzesten Pfad zu den nächsten Knoten von A zu berechnen. Dies ist ein Vorwärtspfad. Berechnen Sie dann rekursiv den Weiterleitungspfad für jede besuchte Aufgabe. Das Ergebnis ist ein Baum. Zum Beispiel:

          EIN
      BC
    DE

nn1n2n20

n=n=1

n

yemelitc
quelle
6
Vielen Dank, dass Sie uns Ihre Gedanken mitteilen. Normalerweise wird in der Informatik unter einem Algorithmus verstanden, eine Folge von Bits als Eingabe zu akzeptieren und eine andere Folge von Bits auszugeben. Mit diesem Standardverständnis sehe ich nicht, wie diese Antwort sinnvoll sein kann. Wenn Sie eine andere Vorstellung von Algorithmus haben, wäre es meiner Meinung nach hilfreich, wenn Sie die Frage dahingehend bearbeiten, was Sie unter Algorithmus verstehen (da Sie den Begriff anscheinend nicht in einer Weise verwenden, die der Standardverwendung von entspricht) Begriff, wie ich es verstehe).
DW
Die Eingabe kann einfach eine Zahl sein (die Anzahl der Ressourcen). Dies wirkt sich auf die Anzahl der zusätzlichen Berechnungen aus, die der Algorithmus durchführen muss. Ich werde die Antwort bearbeiten, um ein konkreteres Beispiel zu liefern.
Yemelitc
Vielen Dank für Ihre Bearbeitung - das macht es viel klarer. Ich sehe jetzt, dass Sie die Kosten für die Berechnung der Lösung nicht mit den Kosten für die Ausführung verwechseln, wie ich ursprünglich gedacht habe. Aber jetzt sind wir in der üblichen Situation. Erstens dauert das Lesen der Eingabe mindestens linear. Zweitens sind es nicht die schwierigen Fälle, in denen Sie einen kleinen Baum und eine Milliarde Menschen geben, sondern in denen Sie einen großen Baum und relativ wenige Menschen geben. (Wenn Sie mir zum Beispiel eine Million Bits erlauben, wähle ich einen Baum mit ungefähr tausend Eckpunkten und gebe Ihnen fünf Personen, keinen Baum mit fünf Eckpunkten und tausend Personen.)
David Richerby
Genau. Es scheint, als wären wir alle ziemlich kritisch darüber gelandet. Aber hoffentlich bekommst du meine Vorstellung von „Input als Ressource“: Egal wie groß die Arbeit ist, je mehr Menschen, desto besser. Immer noch im asymptotischen Sinne haben Sie definitiv Recht, ich sollte nur nicht negative ganze Zahlen dafür verantwortlich machen.
Yemelitc