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
-1
votes
0answers
14 views

Is this context free grammar ambiguous?

CFG: stmt → IF expr THEN stmt | matchedStmt matchedStmt → IF expr THEN matchedStmt ELSE stmt | other i got those parse trees and i think is unambiguous. Is this true ?
1
vote
0answers
18 views

How to prove that some function $f$ is {time,space}-constructible function

Is there a standard method to prove or disprove that some functions are or aren't time or space constructible? can you give me a way to check them ? or an example ?
-3
votes
1answer
35 views

What is the contradiction of statement "if $n^2$ is odd then n is odd"

In my opinion the contradiction should be-: If $n^2$ is even then n is even. But it is written in my discrete mathematics book that, "n is even then $n^2$ is odd". How do we find ...
1
vote
1answer
23 views

What do we conclude from diagonalization principle?

I understand $R_{fa}$ etc. I understand why the diagonals are higlighted. I understand D={a,d,f}. But I don't understand what is the conclusion we derive from this?
1
vote
1answer
20 views

Karatsube-Ofman runtime complexity computation

I have a question and didn't understand the solution, since we didn't take how to do it in the lecture and it's not explained in the solution sample. Question: One can generalize the Karatsube-Ofman ...
2
votes
1answer
121 views

How to verify-: A language over Σ is also a language over any alphabet that is a superset of Σ?

Context-: A language over Σ need not include strings with all symbols of Σ Thus, a language over Σ is also a language over any alphabet that is a superset of Σ. https://www.univ-orleans.fr/lifo/...
0
votes
2answers
70 views

Validity of proof by contradiction

I had a doubt in the proof by contradiction technique. Under this technique, we assume the negation of what we want to prove as true, then show that assuming so generates a contradiction. Since a ...
1
vote
1answer
23 views

Is it common to prove that some code is the simplest way to achieve something?

I have a simple program which achieves a certain functionality. I’m interested to know if it can be proven that the steps in the program are the theoretically simplest way to achieve those results. Is ...
0
votes
0answers
43 views

Suppose f(n) = O(h(n)) and g(n) = O(h(n)). Is f(n) * g(n) = O(h(n) * h(n))?

I understand this should be a relatively easy proof, but I can't seem to understand how to do it. I know that, by Big O definition: there exists some value $c_1$ where $f(n) \le c_1 \cdot h(n)$ for ...
1
vote
0answers
33 views

NP-hardness proof of an optimization problem with real values and real input in the decision problem

Question - Let's suppose we have an optimization problem $\mathcal{P}$ with a real-valued measure function and the decision version of the optimization problem $\mathcal{P}_D$ (please see definitions ...
2
votes
0answers
88 views

NP-hardness proof of an optimization problem with real values and rational input in the decision problem

I'm studying complexity theory and I have the below question regarding $NP$-hardness proofs of optimization problems with real values. Any reference is much appreciated. For the question, take the ...
1
vote
1answer
120 views

Invariant vs Assertion vs lemma

I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate ...
0
votes
3answers
56 views

Mutual Friends in a Network?

I always seem to have trouble finding a formal way to analyze this (be through proofs or whatever). The problem statement is as such: If A and B are friends, and B and C are friends, then A and C are ...
1
vote
1answer
31 views

M does not accept [M] | 'Correction' of proof possible?

The language $D=\{[M]|M([M])=0\}$ is not decidable because of the following argument: Suppose there was a $TM \space M_D$ that decides $D$. Then if we gave $M_D \space [M] $, there would be two ...
0
votes
1answer
39 views

How can I use induction for proving termination of a string rewriting system?

If we have a string rewriting system within the alphabet $\{X,Y\}^*$ and the rule $XY\to YX$. How can we prove by induction that on every string input the system terminates?
1
vote
1answer
129 views

Proof that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ s.t. a DFA accepting $A_k$ has $k$ states but no less

I am trying to prove that for every $k > 1$, there exists a language $A_k \subseteq \{0, 1\}^*$ such that a DFA accepting $A_k$ has $k$ states but no less. I thought about proving this in two ways: ...
1
vote
1answer
54 views

How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?

I know how to prove longest-path problem by reducing Hamiltonian Path problem. Here I want to prove NP-hardness of a Hamiltonion Path problem by reducing longest-path problem. (pretend we know longest-...
0
votes
1answer
56 views

Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"

Do two halting Turing machines accept the same language? Proof that it is undecidable(credit to another user on this website: "Tom van der Zanden"): Let M be an arbitrary Turing machine. Let ...
0
votes
1answer
31 views

Proving that $f(n) \not\in O(n)$ given that $f(n) \in \Theta(n^2)$ and the formal definitions of Big-Oh and Theta

So far I've understood that because of the definition of $\Theta$, we have $c_1n^2 \le f(n) \le c_2n^2$. I'm not sure how to proceed from there.
1
vote
1answer
107 views

How can I prove the following problem is NP complete?

The problem: I have a list $\displaystyle S=\{s_{1} ,s_{2} ,\dotsc ,s_{n}\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\{s_{i} ,s_{j}\} \in \mathbb{N}$, $\displaystyle g\...
1
vote
2answers
161 views

Finding an algorithm to return the $\log n$ largest element in an array

I have just proved that for every $\alpha, \beta>0 : (\log n)^\alpha=O(n^\beta)$. Now, given an array of $n$ elements, I want to find an efficient comparison based algorithm for finding the $\log n$...
1
vote
0answers
22 views

Proving Minimum Sequence Disjoint Set

Prove that 9 is the minimum number of calls to make-set, union-set, find-set such that a disjoint set union using weight (number of nodes) by path compression and disjoint set union using rank (upper ...
1
vote
1answer
80 views

Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text

I was going through the automata text by Peter Linz. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds. Every context-sensitive language L is ...
2
votes
0answers
21 views

How to use butterfly network for data copy?

I know butterfly networks (and benes as well) allow routing a packet from any input to any output node. Congestion is $\sqrt{n}$ but with bene it can be $1$. Now assume that in a butterfly network, ...
1
vote
1answer
42 views

Given CFG generates all words with equally many 0s and 1s

Here is an exercise from an introduction to computation class: Show that the following context-free grammar $G$ generates the language $L$ of words over $\{0,1\}$ with an equal number of $0$s and $1$...
1
vote
1answer
9 views

Inductive sequence of words in a biprefix code

Let $X = X_1 \cup X_2$ a code on an alphabet $A$, with $X_1$ a biprefix code and $X_2$ a uniform code, with $m(X_1) < m(X_2)$, i.e. the maximal length of the first is strictly lower than the second....
1
vote
1answer
49 views

Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$

I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my ...
0
votes
1answer
86 views

Pumping Lemma Proof (Type of wcw language)

I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma. The structure of the language i think can be explained ...
1
vote
1answer
20 views

Proving using a SAT solver that KB entails D

Suppose you're given this KB: $$KB = (A, A ⇒ B, A ⇒ C, B ∧ C ⇒ D)$$ How would you show using a SAT solver that $KB \vDash D$?
0
votes
0answers
58 views

Proof that CSL ⊊ REC

I'm trying to prove that a context sensitive language ⊊ Turing-acceptable language. I was thinking of working out the complement of the language $A$, where $A$ consists of all words $w$ such that $M_w$...
0
votes
0answers
77 views

Gale-Shapley Stable matching where one man's preference list changes

Given $n>1$ women and men. Let $M$ be the stable matching given by the Gale-Shapley algorithm with men proposing. Is there a stable matching instance such that: changing one man's preference list ...
1
vote
2answers
61 views

Constant terms at each level of a recursion tree

In CLRS, exercise 4.4-5 the following question is asked: Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$ In my recursion tree, the ...
1
vote
1answer
56 views

Proving big-theta complexity with constants in $f(n)$

I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c_1$, $c_2$, and $n_0$ such ...
1
vote
2answers
168 views

Big theta notation in substitution proofs for recurrences

Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$. For example, on page 91, the recurrence $$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$ is written like so in ...
1
vote
0answers
31 views

Equivalence of two approximation algorithms for min Steiner tree

I learned two approximation algorithms for the min Steiner tree: The first algorithm: 1- Compute the metric closure G' of G. 2- Compute a min spanning tree T' of G' 3- Construct the union U of the ...
4
votes
3answers
221 views

Algorithm for solving a mixed integer programming problem in polynomial time?

I have the following mixed integer programming (MIP) problem: $$ \begin{array}{rll} \text{Maximize } & z=k \\ \text{subject to } & a_ik - m_i \geq 0 & (i=1,\dots,n) \\ & b_ik - m_i \...
-2
votes
1answer
34 views

Decidability of whether $w \in L(M_1) \setminus L(M_2)$

I'm studying for my finals and I came across this question from past exams: Is the following language decidable? $$ L = \{ \langle M_1,M_2,w \rangle \mid w \in L(M_1) \setminus L(M_2) \}. $$ How can ...
1
vote
0answers
146 views

How can I simulate nested WHILE loops in a theoretical programming language to show Turing completeness?

PRE-WORK-POST is a theoretical programming language with the following structure, where P,Q and R are LOOP program: $$\text{PRE} \ P \ \text{WORK} \ Q \ \text{POST} \ R \ \text{END}$$ First $P$ is ...
4
votes
1answer
57 views

Proving equivalence of two substitutions by induction

I'm trying to prove the following reduction: $$ t\{x:=u\}\{y:=v\} = t\{y:=v\}\{x:=u\{y:=v\}\} $$ under the following assumptions: $x \neq y$ $x$ is not a free variable of $v$ (in symbols, $x \...
2
votes
0answers
29 views

How to specify mutated types mathematically?

Say I have an object which I pass to a method, and the method returns that same object, just mutated. So it goes like this: ...
-1
votes
1answer
180 views

How to show a language is Partially Decidable?

I am trying to solve some questions on partial decidability of languages and I am getting confused in how to construct proper arguments through the idea of Universal Turing Machine. I am not posting ...
0
votes
0answers
47 views

How to create mathematical proof of TSP and SLAP equivalence?

In my thesis, I'm dealing with SLAP (storage location assignment problem) -- which is finding optimal distribution of products to location slots in a generic warehouse. My aim was to implement ...
0
votes
1answer
335 views

reduction from ALLTM to ETM

I am trying to understand why this "proof" of ETM undecidability is wrong. ALLTM={ < M >|M is a TM, L(M)=∑*} ETM={< M >|M is a TM, L(M)=∅} We know that ALLTM is undecidable, lets ...
1
vote
1answer
29 views

Time complexity of binary search

Proposition: The binary search algorithm runs in $O(\log n)$ time for a sorted sequence with $n$ elements. When justifying this claim, first we say that with each recursive call the number of ...
2
votes
1answer
117 views

Early Deadline First (EDF) scheduling in real-time systems feasibility test proof

I am trying to prove Theorem 6.2 on page 127 of the book Real-Time Systems by Jane W. S. Liu: http://www.cse.hcmut.edu.vn/~thai/books/2000%20_%20Liu-%20Real%20Time%20Systems.pdf It is based on Early ...
1
vote
0answers
60 views

How to prove a statement in regular expression?

I cannot figure out how to go about proving this statement in regular expression. $$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$ Here's what I have ...
0
votes
0answers
54 views

When are existential quantifiers in the intuitionistic propositional calculus eliminable and when not

I am so ignorant I don't even know where should I ask this - on FOM? On mathoverflow? On cstheory? So please consider as sort of a meta-question readdressing me in case you think this is a wrong site. ...
0
votes
0answers
153 views

How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language: $$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$ is undecidable? I looked at the proof for $A_{TM}$ ...
0
votes
3answers
252 views

Prove (p → ¬q) is equivalent to ¬(p ∧ q)

I need to prove the above sequent using natural deduction. I did the first half already i.e. I proved $(p\rightarrow\neg q)\rightarrow \neg (p \wedge q)$, but I'm stuck on where to start for the ...
1
vote
1answer
52 views

Why discriminate the base case allows me to complete the induction proof?

I have a successful completed proof which used induction. but I essentially proved the goal on the base case by tactic discriminate. Why is this induction proof ...

1
2 3 4 5
13