Exercises
Multiple Choice
Articles
Open Problems
Login
13 exercises
Topic:
Complexity Theory
x
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Undergraduate
By
John Doe
on Nov. 3, 2012 | Updated Dec. 6, 2017
Direct reduction from Graph Homomorphism to SAT
The decision problem \(GraphHomo\) is defined as follows: \(GraphHomo = \{\langle G, H\rangle \mid \text{there is a graph homomorphism from G to H}\}\) Give a direct reduction from \(GraphHomo\) to …
Computer Science
Mathematics
Complexity Theory
Graph Theory
Logic
np
reduction
sat
0
Graduate
By
domotorp
on June 6, 2012 | Updated Dec. 6, 2017
Read Once Promised Majority
Suppose the input is \(n\) numbers from \(1\) to \(n\), separated by commas and we know that one of the number occurs more than \(n/2\) times. How can we decide which if we can read the input tape onl…
Computer Science
Puzzles
Complexity Theory
Puzzles
read once
0
Undergraduate
By
domotorp
on June 11, 2012 | Updated Dec. 6, 2017
Non-double words form a context-free language
Define double words whose first and second half is the same, e.g. baba or aaaa but not abba, bab or bababa. Prove that over a finite alphabet the language of non-double words is context-free. (Context…
Computer Science
Complexity Theory
formal languages
0
Undergraduate
By
Shiva Kintali
on Nov. 13, 2012 | Updated Dec. 6, 2017
Turing reducibility
Let \(A \leq_T B\) denote that language \(A\) is Turing reducible to language \(B\). Prove the following : Show that for any two languages \(A\) and \(B\) a language \(J\) exists, where …
Computer Science
Complexity Theory
turing reducibility
0
Graduate
By
Shiva Kintali
on May 7, 2012 | Updated Dec. 6, 2017
Graph Isomorphism, BPP and RP
The Graph Isomorphism Problem is to determine whether two given graphs are isomorphic to each other. Prove that if Graph Isomorphism is in BPP then it is in RP.
Computer Science
Complexity Theory
graph isomorphism
0
Graduate
By
Shiva Kintali
on June 19, 2012 | Updated Dec. 6, 2017
Primality is in NP $\cap$ co-NP
Primality is the following problem : Given a positive integer \(n\), is \(n\) prime ? Note that the size of the input is the number of bits used to represent \(n\). Easy : Show that Primality…
Computer Science
Mathematics
Complexity Theory
Number Theory
primes
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Dec. 6, 2017
Basics of decidability
State whether each of the following statements are TRUE or FALSE. Your answers should be accompanied by a proof. Every recognizable set has a decidable subset. Any subset of a recognizable language …
Computer Science
Complexity Theory
basics
true or false
undecidability
0
Graduate
By
Shiva Kintali
on Aug. 13, 2012 | Updated Dec. 6, 2017
Integer Factoring is in NP $\cap$ co-NP
Formulate an appropriate decision version of Integer Factorization and prove that it is in NP \(\cap\) co-NP. There are two ways of proving this : (Easy) Use the fact that Primality is in P. Witho…
Computer Science
Mathematics
Complexity Theory
Number Theory
factoring
NP completeness
0
Graduate
By
Shiva Kintali
on June 10, 2012 | Updated Dec. 6, 2017
Size of monotone circuits
Prove that there is a monotone boolean function \(f(x_{1}, x_{2},\dots,x_{n})\) such that any circuit (consisting of only AND, OR gates) computing \(f\) requires at least …
Computer Science
Complexity Theory
circuit complexity
lower bound
monotone function
0
Graduate
By
John Doe
on Nov. 3, 2012 | Updated Dec. 28, 2017
Computability of the space complexity of Turing machines
Show that the space complexity of Turing machines is computable. The space complexity is the partial function \(s:\Sigma^* \times \Sigma^* \to \Sigma^*\) defined as …
Computer Science
Complexity Theory
computability
space complexity
turing machine
1
2
next page »
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
jee
jee main
statistics
variance
equation
jee 2016
jee advanced
jee mathematics
imo
imo 2015
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×