# All Questions

42,752 questions
Filter by
Sorted by
Tagged with
28 views

### Proving correctness of Polynomial reduction

Given a problem A is NP-Hard and A ≤𝑝 B, is there a way to prove that B is also NP-Hard?
32 views

### Can a machine that, given infinite space, functions as a non deterministic turing machine actually exist in the real world?

I am a novice when it comes to computer science. But I know that traditional quantum computers are not non deterministic Turing machines. But it seems to me that the principles of quantum mechanics ...
81 views

### Vertex Cover with minimum degree 1

In Special Vertex Cover, we are given an undirected graph $G$, and an integer $k\in \mathbb{N_0}$. The objective is to decide whether there exists a vertex cover $S$ of $G$ of size at most $k$ such ...
19 views

### Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
13 views

### Relation between time complexity and conditional statement [closed]

I need examples for the types of time complexity for conditional statement
18 views

### Control Flow Graph - How to represent returns in code

Consider the following program int someCode1(int x){ if (x < 0) return 0; else return x; Last Statement;} Last statement could be either "printf(...
34 views

### How to solve $T(n) = T(27n/9) + n^3$ with substitution method

I'm trying to solve this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?
36 views