Questions about methods and techniques for proving theorems.
3
votes
2answers
71 views
MAX 10-SAT Algorithm
The MAX k-SAT problem is:
“Given a set of clauses C1,…,Ck, each of length k, over a set of
variables x1,…,xn, find a truth assignment that satisfies as many of
the clauses as possible.”
I'm ...
5
votes
2answers
89 views
Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$
Hi I've read this lemma in my book:
Lemma 2.1. Let $p(n) = \sum_{i=0}^{k} a_in^i$ denote any polynomial and assume $a_k > 0$. Then $p(n) \in \Theta(n^k)$
Proof. It suffices to show that ...
3
votes
2answers
125 views
Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular
Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular.
These are the things that I would use to start.
As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular.
Let ...
1
vote
1answer
35 views
Showing transitivity of PSPACE?
For the following question:
If B is an element of PSPACE and A is an element of PSPACE-Complete, and A polynomial reduces to B, then B is an element of PSPACE-Complete.
I am trying to prove this, ...
2
votes
1answer
61 views
How to show that L = L(G)?
Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is ...
12
votes
3answers
202 views
What are common techniques for reducing problems to each other?
In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as ...
4
votes
1answer
101 views
How to show that a function is not computable?
I know that there exist a Turing Machine, if a function is computable. Then how to show that the function is not computable or there aren't any Turing Machine for that. Is there anything like a ...
4
votes
2answers
112 views
A pumping lemma for deterministic context-free languages?
The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove ...
0
votes
1answer
78 views
4
votes
1answer
68 views
A procedure for Topological sort, proof for its correctness
Definition: A preserved invariant of a state machine is a predicate, $P$, on
states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$,
then $P(r)$ holds.
...
0
votes
0answers
26 views
1
vote
0answers
21 views
Potential function in amortized analysis [duplicate]
I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there).
...
3
votes
2answers
151 views
Acyclic Tournament Digraphs and Hamiltonian Paths
I am studying MIT OCW lecture notes but they do not have solutions for the following problem.
Directed Acyclic Tournaments
In a round-robin tournament, every two distinct players play against each ...
1
vote
1answer
82 views
Closure of regular Language - Transition Function : Sipser Proof
I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser.
I have ...
1
vote
2answers
49 views
Proving non-confluency and adding an equation to make it confluent and terminating
I currently have a system that has {f(a) = b, f(f(x)) = x} (part of an exam question - look at page 5 - exercise 1).
To start off with proving non-confluency, I am ...
7
votes
0answers
79 views
Solving divide & conquer reccurences if the split-ratio depends on $n$
Is there a general method to solve the recurrence of the form:
$T(n) = T(n-n^c) + T(n^c) + f(n)$
for $c < 1$, or more generally
$T(n) = T(n-g(n)) + T(r(n)) + f(n)$
where $g(n),r(n)$ are some ...
5
votes
2answers
96 views
Proof-sketch on the language accepted by a Turing machine
Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$
1
vote
1answer
109 views
How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$?
I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma:
$L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0 \}$
Does this indicate that $S = 2$, so we ...
2
votes
1answer
70 views
How do I explain that a polynomial time reduction is in fact polynomial time?
I have as an assignment question to show that $QuadSat=\{\langle\phi\rangle\mid\phi$ is a satisfiable 3CNF formula with at least 4 satisfying assignments$\}$ is $\sf NP$-Complete.
My solution is as ...
2
votes
0answers
79 views
Proof of SAT is randomly reducible to UNIQUE-SAT
I am asking for help to explain some crucial points of the central lemma and it's proof of famous paper NP is as easy as detecting unique solutions by L.Valiant and V.Vazirani.
The proof can be found ...
11
votes
1answer
133 views
Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we ...
3
votes
2answers
74 views
Convergence of Simulated Annealing Based Algorithms
I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge ...
1
vote
1answer
57 views
Solving a simple recurrence
I'm having a real hard time solving recurrences using the substitution method.
Show that: $T(n) = T(n/2) + 1$ is $O(\lg n)$
I thought this to be relatively easy:
We have to show that $T(n) \leq c ...
0
votes
0answers
44 views
How i can use Mathematical induction to prove CFG production? [duplicate]
If I have production $G_n$
$S \rightarrow A_i b_i \quad$ for $1 \le i \le n$
$A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$
Prove $G_n$ is sub-productions from $2n^2 ...
3
votes
2answers
65 views
Proof of the Stable Matching Problem
Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem.
Theorem 1.2.3 - page 12:
In a man-optimal version of stable matching, each woman has worst
partner that ...
3
votes
1answer
64 views
Languages that satisfy the pumping lemma but aren't regular?
Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ ...
2
votes
1answer
53 views
The use of multiset ordering in proving termination
Based on the definition of a multiset and the information in this paper, why do we use multisets in proving the termination of a program?
Is not the well-founded order enough?
6
votes
4answers
177 views
Questions about amortised analysis
As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the ...
1
vote
3answers
90 views
Search spaces and computation time
This question follows on previous questions (1), (2), where we define an initial space of possibilities and reason about how a solution is chosen from that.
Consider a problem P where we are given:
...
4
votes
1answer
70 views
What are some good hints for proving non-regularity with the pumping lemma?
My CS Theory Professor said that when proving that a language is not regular by the Pumping Lemma, that there are some 'tricks' for solving languages more complicated that something like $L = \{a^{n} ...
3
votes
3answers
148 views
Proof by restriction: when is it valid to restrict to a special case?
I was reading a few notes on Proof by Restriction and I am confused:
A Valid Proof by Restriction is the following:
Directed Hamiltonian Cycle Problem is NP Complete because if we look only at ...
2
votes
2answers
95 views
Is the undecidable function $UC$ well-defined for proving the undecidability of Halting Problem?
I am new to Computability Theory and find it is both amazing and confusing. Specifically, it is difficult for me to get through the undecidability of the well-known Halting Problem.
Halting ...
1
vote
1answer
39 views
Progress of algorithms in problem spaces
Continuing in the vein of two prior questions (1) and (2), we started with sorting, where we had
a set of $n!$ input possibilities
a goal space of only one element consisting of the one correct ...
2
votes
0answers
81 views
k-Trees Graph Coloring
There is an exercise in Distributed Algorithm I have some difficulties to solve. There are few ideas, however nothing useful at the time. I will appreciate any help with it.
Graph $G$ is a $k$-tree ...
3
votes
0answers
59 views
Proof of message complexity on the network
I try to provide a strict and mathematical rigorous proof to the following problem in Distributed Algorithms.
Prove or make a contradiction: if to vertices $a$ and $b$ on the network $G$ are located ...
2
votes
2answers
210 views
How to show that given language is unambiguous
Given following grammar:
$$
\begin{align}
S \rightarrow &A1B \\
A \rightarrow & 0A \mid \varepsilon \\
B \rightarrow & 0B \mid 1B \mid \varepsilon \\
\end{align}
$$
How can I show that ...
3
votes
2answers
150 views
Proving regularity via equivalence classes
Given two regular languages $L_1$ and $L_2$, we define a new language
$$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$
How do I show that $L$ is ...
3
votes
2answers
71 views
Lower bound on size of proof that a list of integers is sorted
Suppose we have a list of unbounded integers, written in binary, and we want to write a (formal) proof that the list is sorted in ascending order.
Such a proof might look (informally) like: "2 < ...
4
votes
1answer
62 views
Proofs based on narrowing down sets of possibilities
Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows.
First, the comparison sorting lower-bounds proof was recited:
For $n$ ...
3
votes
1answer
129 views
How to show composition of one way function is not such?
I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function?
Specifically: Say $f$ and ...
0
votes
1answer
63 views
How to determine the polynomial runtime of an NP reduction?
To show that a NP problem is NP-complete, we also have to show that $L \leq_{p} L'$ , where $L$ is proven NP-complete and you have to prove $L'$ also is. The thing I am confused is how in all ...
2
votes
2answers
138 views
Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages
So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\text{shrink}_a(L) = \{\text{shrink}_a(w)\mid w\in L\}$ and where ...
2
votes
1answer
69 views
Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$
$T(n)=2T(n/2) + n\log^2(n)$.
If I try to substitute $m = \log(n)$ I end up with
$T(2^m)=2 T(2^{m-1}) + 2^m\log^{2}(2^m)$.
Which isn't helpful to me. Any clues?
PS. hope this isn't too localized. ...
1
vote
2answers
133 views
Proof of linear search?
Consider the searching problem:
Input: A sequence of $n$ numbers $A=(a_1, a_2, \ldots , a_n)$ and a value $v$.
Output: An index $i$ such that $v = a_i$ or the special value NIL if $v$ does ...
2
votes
1answer
141 views
Invariant Proof of For Loops?
From CLRS (third edition, page 19), there is a footnote:
When the loop is a for loop, the moment at which we check the loop invariant just prior to the first iteration is immediately after the ...
6
votes
1answer
135 views
Generalizing the Comparison Sorting Lower Bound Proof
Let's start with the comparison sorting lower bound proof, which I'll summarize as follows:
For $n$ distinct numbers, there are $n!$ possible orderings.
There is only one correct sorted sequence of ...
3
votes
1answer
321 views
NP-Completeness - Proof by Restriction
I'm reading Garey & Johnsons "Computers and Intractability" and I'm at the part "Some techniques for solving NP-Completeness". Here's the text about Proof by Restriction:
Proof by restriction ...
6
votes
3answers
184 views
Proving the language which consists of all strings in some language is the same length as some string in another language is regular
So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
2
votes
1answer
86 views
Runtime of the binary-GCD state machine
I am doing self study from MIT OCW exercises and I could not understand this question.
The following rules define the binary-GCD state machine working on states in $\mathbb{N}^3$ with start state ...
0
votes
0answers
27 views
The binary-GCD algorithm state machine [duplicate]
Possible Duplicate:
Runtime of the binary-GCD state machine
Hello I am doing self study from MIT OCW exercises and I could not understand this question. Can anyone explain me,
First, why ...
