TheoComp
asdf
asdf
Set of flashcards Details
| Flashcards | 23 |
|---|---|
| Language | Deutsch |
| Category | Computer Science |
| Level | Primary School |
| Created / Updated | 12.06.2025 / 14.06.2025 |
| Weblink |
https://card2brain.ch/box/20250612_theocomp
|
| Embed |
<iframe src="https://card2brain.ch/box/20250612_theocomp/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
|
Create or copy sets of flashcards
With an upgrade you can create or copy an unlimited number of sets and use many more additional features.
Log in to see all the cards.
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:
Membership: They themselves lie in NP.
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.
-
- 1 / 23
-
