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
vote
0answers
23 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
62 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 ...
4
votes
0answers
53 views

How to prove that the problem $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ is undecidable?

Lately I came across a problem: $\text{"If $L$ is a context-free language, then, is $\overline{L}$ also context-free?"}$ And I need to comment on its decidability. Now I know that context free ...
1
vote
1answer
100 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
40 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
26 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
38 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
50 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
46 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
34 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
23 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
81 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
98 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
21 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
47 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
18 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
37 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
46 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
73 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
18 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
52 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
68 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
52 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
47 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
88 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
30 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
206 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
30 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
130 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
54 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
101 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
45 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
0answers
252 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
28 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
102 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
56 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
14 views

Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
0
votes
0answers
52 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
118 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
186 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
47 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
vote
1answer
34 views

Converse proof for random coding capacity of AVC

I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof ...
0
votes
2answers
56 views

Are different assignments allowed for the implication graph proof of 2-SAT being in P?

One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor ...
4
votes
0answers
220 views

Can every sentence of first-order logic be converted into an equisatisfiable equation in Boolean algebra?

There may be some theoretical literature, unknown to me, that addresses this question. If possible, I would like a practical approach to this problem. My attempt involves the use of an equational ...
1
vote
0answers
39 views

why is behaviour of simpl differ so much after a commutative operation and how to inspect simpl?

In Coq, while trying to prove a lemma mult_n_Sm for mult_comm, I have this equation in a proof: ...
3
votes
1answer
35 views

Why isn't plus_assoc rewriting correctly?

First I have plus_assoc ready. Theorem plus_assoc : forall n m p : nat, n + (m + p) = (n + m) + p. for simplicity we omit the ...
0
votes
1answer
26 views

How do you prove these string/number radix encoding/decoding algorithms work?

A while back I learned of these great algorithms: ...

1
2 3 4 5
13