Windows 10 Start Menu search not working for installed apps

I am facing a problem with Windows 10 OS Home Edition, updated 14th August 2017 [Yesterday]. I am not able to search installed applications.

NOTE: I ran every command and program as administrator

1. Deleting and Rebuilding the indexes


2. 
   

   Verifying that both

   
   

   C:\Users\\AppData\Roaming\Microsoft\Windows\Start Menu
C:\ProgramData\Microsoft\Windows\Start Menu\Programs
   are included in indexing.

   
   


3. 
   

   Running Get-AppXPackage -Name Microsoft.Windows.Cortana | Foreach {Add-AppxPackage -DisableDevelopmentMode -Register "$($_.InstallLocation)\AppXManifest.xml"}

   
   


4. 
   

   Restarting Cortana application and Windows search service

   
   


5. Restarted Explorer app


6. Restarted the system

Nothing working

I recently found out that there is strong connection between

C:\Users\\AppData\Local\Packages\Microsoft.Windows.Cortana_randomsuffix\LocalState\ConstraintIndex\Apps_{some-uuid}

and the

Search Results

If i make changes to the file Apps.index in directory Apps_{some-uuid} just like renaming it, search doesn't find apps that were coming in results before.