# Questions tagged [complexity-classes]

Questions about relationships between complexity classes.

350 questions
Filter by
Sorted by
Tagged with
16 views

### I want to know the complexity of this following code [closed]

include include include void main() { char p[10][5],temp[5]; int i,j,pt[10],wt[10],totwt=0,pr[10],temp1,n; float avgwt; printf("Enter no of girls:"); scanf("%d",&n); for(i=0;ipr[j]) { temp1=pr[...
16 views

61 views

### Proving a pattern exist in a string without revealing where

Some time ago i read the following problem (i don't remember the article from which i read it from) : "Suppose you are given a picture where the goal is to find waldo (from the game where is waldo), ...
80 views

### Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n))$. I´ve made a program to check this statement and it ...
21 views

### Proof by padding: $\textsf{TIME}(t_1(n)) = \textsf{TIME}(t_2(n)) \implies \textsf{TIME}(t_1(f(n))) = \textsf{TIME}(t_2(f(n)))$

I've been given the task of proving the statement in the title, which I found out it should be called the translational lemma by means of a padding argument; $f$, $t_1$ and $t_2$ are three ...
31 views

### how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

how proof ${\ \ NPC \ \ \bigcap \ \ CO-NPC \ne \varnothing }$ then ${NP = P ? }$
145 views

### Have any natural complexity classes been proven not to be closed under complement?

Many important (non-deterministic) complexity classes like NP are believed not to be closed under complement. But have any of them been proven not to be? I'm sure one could construct some contrived ...
125 views

69 views

### {0,1}* ∈ P class?

I have the following question about complexity time classes. Given the language $L = \{0,1\}^*$, is it inside the class P or not? $$L = \{0,1\}^∗ ∈ P?$$
58 views

### If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?

The following question was asked on a quiz: Let S be an NP-complete problem, and Q and R be two other problems (that we don't know much about). If we now know that Q is polynomial time reducible (i....