Time complexity analysis of 2 arbitrary algorithms – prove or disprove

We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size.

We denote the worst time complexity of each one by $ g_A(n),g_B(n)$

Also, we know there’s a positive function $ f(n)$ such that $ g_A(n)\in\Omega(f(n))$

Is it possible that $ g_B(n)\in\Omega(f(n))$ ? Is it necessary?

It seems naive to think that it’s necessary, but I can’t figure out to contradict it.

Prove or disprove the following language is context free

The language $ L$ defined as: $ L = \{wtw^R | w,t \in \{0,1\}^\star \text{ and } |w| = |t| \}$

It looks like the language can be “pump” by context free pumping lemma, but pumping lemma doesn’t prove the language is context free. So I’m thinking to build a PDA that recognized it. But I’m stuck on constructing the PDA, my initial thought is using nondeterminism to guess the string $ w$ and $ t$ , then compare the values after $ t$ which is string $ w^R$ . But still hard for me to come up a whole construction at this moment, any suggestions?

using pumping lemma to disprove context free

Question: Disprove $ L$ is context free where $ L = \{w ∈ \{1\}^\star |w| \text{is a perfect square}\}$

I’m learning pumping lemma recently, so I’m sharing my thoughts here to make sure I’m on the right track. According to pumping lemma definition, there exits pumping length $ p$ such that any string $ w \in L$ of length $ \geq$ $ p$ can be break as $ w = uvxyz$ , where $ vy \geq 1$ , $ |vxy| \leq p$ , and for all $ i\geq 0$ , $ uv^ixy^iz \in L$ . First we choose $ s = 1^{p*p}$ . Break $ s$ into $ uvxyz$ where $ vy \geq 1$ and $ |vxy| \leq p$ . Hence, we have three cases such either $ v$ or $ y$ contains all 1’s up to $ p$ or $ |v| + |y| \leq p$ . For instance, if we let $ p$ = 2, then we have w = 1111, breaking into $ uvxyz$ , by pumping lemma, since $ vy \geq 1$ and $ |vxy| \leq p$ , either $ v$ has 11, or $ y$ has 11 or $ v$ has 1 and $ y$ has 1. Thus, choosing $ i$ = 2, we have $ w’$ = $ uv^2xy^2z$ = $ uvvxyyz$ , either $ v$ or $ y$ has two 1’s. The word $ w’$ is increasing number of 1’s such that $ w’$ = 111111 which is not a perfect square number. Thus $ uv^2xy^2z$ $ \notin L$ and we reach contradiction, so $ L$ is not context free. Any suggestions?

How do I prove or disprove the following statements?

I have to prove or disprove the following statements.

a) ≈(L(X)) ⊆ ≈(L(Y)) ⇒ ~(X) ⊆ ~(Y)

b) L(X) ⊆ L(Y) ⇒ ~(X) ⊆ ~(Y)


Definitions:  DFA:M=(K,Σ,q0,δ,F) x~y : ∃q∈Q (q0,x) |-- (q,λ) and (q0,y) |-- (q,λ) x≈y : ∀z∈Σ* xz∈L ⇔ yz∈L 

My problem is the formal proof.

I could show that L(X) ⊆ L(Y) ⇒ ~(X) ⊆ ~(Y) with the help of an exmaple, but that doesn’t show that it applies to all.

And the main problem is to show ~(X) ⊆ ~(Y) or ≈(L(X)) ⊆ ≈(L(Y)), because I don’t really get what that means and when or why it is a subset.

Maybe on of you has an idea to prove or disprove the statements.

Prove (disprove) that a document was created with a specific software build

I’m creating some software that essentially enforces a specific process for creating specific documents. Afterwards, the file is signed with the user’s key (USB token not related to the software). Recently there came a stakeholder suggestion to also sign it with the software’s key to prove the process was followed.

But anyone could pull the key from the software and sign anything with it. So how could I include something in the file that confirms (or allows to disprove that) it was created with an authorized build of the software?

Doesn’t matter if the copy is legit or not, just that it’s not been modified.

I’ve narrowed down the threat model to two cases:

  • A. Someone (average solo developer) alters the software, or creates a replacement, to save time, then blames us when things go wrong. I need a way to show “It wasn’t our build”.
  • B. A lawyer claims the document is meaningless because anyone could have done A. The good guys need to show it’s not trivial and there were some protections against that.

The software needs to work mostly offline, so online authentication on every signature is not acceptable. The project’s far too small for anything with the monstrousness of Denuvo. But I still feel there’s got to be a simple solution that I’m too blind to see.

I have considered using the user’s token to encrypt/decrypt the signing certificate, but it has to be supplied to a proper build, and can’t be too cumbersome (we already have a problem with a longer process than desirable). Thought a bit of what code signing could do, but it doesn’t seem to do anything for this case. What am I missing?

Prove or disprove the following proposition

$ L_1^*∪L_2^*⊆(L_1∪L_2)^*$

I actually disproved the opposite proposition $ [(L_1∪L_2)^*⊆L_1^*∪L_2^*]$ and my intuition tells me that this is actually true… I tried to show that the combinations of words in the right group $ [(L_1∪L_2)^*]$ obviously contain all the words from the left group $ [L_1^*∪L_2^*]$ and it’s also very plain to see, but I have no idea how to formalize it.

Any idea how to formally prove it? Thanks.

Prove disprove an existence of mapping reduction between 2 sets

I am currently studying mapping reduction in computational theory and finding it hard to grasp the concept fully.

For reference, consider the following given WHILE-Prog sets:

A = { (p.d) | p doesn’t halt on input d } = Complementary HALT set. B = { p | p halts on exactly one input (the input is unknown) }

Is A < B. meaning, is there a mapping reduction from A to B?


Can someone suggest a hint?

knowing that A belongs to coRE did not help much. B doesn’t seem to belong to either RE nor coRE.

Thanks.