Questions tagged [proof-techniques]

Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.

Filter by
Sorted by
Tagged with
5
votes
2answers
533 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
2k 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
345 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 ...
6
votes
1answer
218 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 ...
20
votes
1answer
767 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 ...
4
votes
2answers
1k 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
2answers
226 views

Solving a simple recurrence [duplicate]

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
59 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 - n$ ...
3
votes
2answers
4k 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 she ...
18
votes
1answer
5k 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$ ...
3
votes
1answer
327 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?
7
votes
4answers
1k 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
253 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
183 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
572 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 ...
5
votes
2answers
423 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
73 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
1k 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
163 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
6k 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
491 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
112 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 < 3,...
4
votes
1answer
93 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$ distinct ...
4
votes
1answer
2k 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
592 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 NP-...
2
votes
2answers
491 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 $\...
5
votes
2answers
1k views

Advantages of amortized analysis

I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis? What I understood: Let say we have 3 three operations a,b,c used 1,2 and 3 times ...
2
votes
1answer
756 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
3answers
2k 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 not appear ...
2
votes
1answer
277 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
794 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
3k 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 ...
8
votes
3answers
489 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
553 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
228 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 does ...
7
votes
3answers
6k views

Recurrence relation for time complexity $T(n) = T(n-1) + n^2$

I'm looking for a $\Theta$ approximation of $$T(n) = T(n-1) + cn^{2}$$ This is what I have so far: $$ \begin{align*} T(n-1)& = T(n-2) + c(n-1)^2\\ T(n) &= T(n-2) + c(n-1) + cn^2\\[1ex] T(n-2)...
4
votes
1answer
280 views

How to prove or disprove that f is computable?

If $f(x_1,\dots, x_n)$ is a total function that for some constant $K$, $f(x_1,\dots, x_n) \leq K$ for all $x_1,\dots, x_n$ then $f$ is computable. I want some hints on how to prove/disprove the ...
5
votes
2answers
611 views

If a predicate is not computable, what can be said about its negation?

Doing the following exercise: Let $\overline{HALT(x,y)}$ be defined as $\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$ Show that it is not computable. Just want to make ...
3
votes
1answer
1k views

Rigorous proof against pseudo random function

I have the following problem: Define the keyed function F as follows: On input k ∈ {0, 1}$^n$ and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function. How do I ...
8
votes
2answers
2k views

Providing Tight Example in Approximation Algorithm Analysis

Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight. Do I now need to come up with an example of generic size $n$ or does it suffice to ...
20
votes
1answer
14k views

How do I write a proof using induction on the length of the input string?

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
1
vote
3answers
196 views

Proving $\Omega(cf) = \Omega(f)$

I'm trying to prove the following lemma: $c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that: $\Omega(cf(n))$...
5
votes
1answer
2k views

Simple Task-Assignment Problem

I have this simple 'assignment' problem: We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike ...
4
votes
4answers
1k views

What approaches are most useful when proving uncomputability of a given function?

I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows: Reduction,...
5
votes
3answers
2k views

Proving a grammar only generates words whose alternating digit sums are multiples of three

This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point. Here's the problem: The following ...
23
votes
3answers
4k views

How to show two models of computation are equivalent?

I'm seeking explanation on how one could prove that two models of computation are equivalent. I have been reading books on the subject except that equivalence proofs are omitted. I have a basic idea ...
7
votes
1answer
891 views

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing $\qquad \...
6
votes
6answers
448 views

Looking for books on creating and understanding theorems targeted at Computer Science

In studying logic to understand verifying programs I have found that there are books on logic targeted at Computer Science e.g. Logic in Computer Science: Modelling and Reasoning about Systems ...
3
votes
1answer
86 views

Showing $A-B$ is a CFL where $A$ is a CFL and $B$ is finite

Show that if $A$ is a context-free language and $B$ is finite, then $A - B$ is a context-free language. I'm just not sure how to use their properties to formally show this. Thanks for all the help in ...
90
votes
11answers
19k views

Solving or approximating recurrence relations for sequences of numbers

In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested ...

1
8 9 10
11
12