c2b_default

TheoComp

asdf

asdf

23
0.0 (0)
M. S.
Study
M. S.
Diese Lernkarten bieten eine grundlegende Einführung in die Theoretische Informatik, insbesondere in die Komplexitätstheorie. Sie behandeln zentrale Konzepte wie P, NP, NP-vollständige Probleme, Turing-Maschinen und Entscheidbarkeit. Die Karteikarten erklären die Unterschiede zwischen verschiedenen Problemklassen, wie deterministische und nicht-deterministische Algorithmen, sowie die Eigenschaften von Sprachen und deren Komplexität. Ideal für Studierende und Interessierte, die die Grundlagen der theoretischen Informatik verstehen und die Zusammenhänge zwischen Problemen und Algorithmen nachvollziehen möchten.
Flashcards
23
Students
1
Language
German
Category
Computer Science
Created / Updated
12.06.2025 / 14.06.2025
  • 1  / 23

Flashcards

Any infinite language is regular

Any finite language is regular

Any infinite language is not regular

The language \(\emptyset\) is regular

The language \(\emptyset\) is context-free

The language \(\{\epsilon\}\) is not regular

Any context-free language is regular

Any not-context free language is infinite

Any regular language is finite

Any context-free language is infinite

If a language L is regular, then L* is regular

If a Language L is regular, then \(\overline{L}\) is regular

Define P

Decision problems solvable by a deterministic Turing machine in polynomial time.

Define NP

Decision problems whose yes-instances can be verified in polynomial time by a deterministic Turing machine (equivalently, solvable in polynomial time by a nondeterministic Turing machine).

Define co-P

Decision problems whose no-instances are solvable by a deterministic Turing machine in polynomial time (i.e., complements of problems in P).
Note: Since P is closed under complement, co-P = P.

Define co-NP

Decision problems whose no-instances can be verified in polynomial time (complements of problems in NP).

Define NP-complete

Problems in NP that are at least as hard as every problem in NP:

  1. Membership: They themselves lie in NP.

  2. Hardness: Every NP problem reduces to them via a polynomial-time many-to-one reduction.
    If any NP-complete problem is solved in polynomial time, P = NP.

Define NP-hard

Problems at least as hard as the hardest problems in NP (every NP problem reduces to them), but not required to be in NP; they may be decision, optimization, or even non-decidable problems.

Palindromes are...

The language \(\emptyset\) is...

Equivalence of two TMs is...

Define co-P again:

co-P is the class of decision problems whose complements are solvable by a deterministic Turing machine in polynomial time:

We know that 2-COLOR decision problem belongs to P. However, is the brute force algorithm for this problem bounded by a polynomial?

A straightforward “brute-force’’ procedure tries every possible colouring of the n vertices with two colours and checks whether any of them respects all m edges. That requires examining 2ⁿ assignments, each verified in O(n + m) time, for a worst-case running time Θ(2ⁿ · (n + m)), which is exponential—not polynomial—in the input size.

The fact that 2-COLOR is in P comes from a different algorithm (e.g. a single BFS/DFS per connected component to test bipartiteness) that runs in O(n + m) time. Thus membership in P guarantees the existence of a polynomial-time algorithm, but the naïve brute-force method is not one of them.

Study